Mail.Ru Cup 2018 Round 2 B. Alice and Hairdresser （bitset<> or 其他）

传送门

题意：

　　给出你序列 a，在序列 a 上执行两种操作；

　　① 0 ：查询有多少连续的片段[L,...,R]，满足 a[L,...,R] > l；

　　② 1 p d ：将第 p 个数增加 d；

思路：

 int n,m,l;

 ll a[maxn];

 int fa[maxn];///a[L,...,x] > l 的最小的L；

 /**

     _bit[0][x]:a[x] > l,_bit[0][x]=1,反之为0；

     _bit[1][x]:a[L,...,R] > l,_bit[L]=1,_bit[L+1,...,R]=0，

     即满足条件的连续片段[L,...R],只将开始位置L赋为1

 */

 bitset<maxn>_bit[];

　　在 m 次操作中，只有出现 a[p] ≤ l && a[p]+d > l 时，才有可能合并区间；

　　即a[L,...,p-1] > l , a[p+1,...,R] > l ,现在 a[p]+d > l 使得 [L,...,p-1] 与 [p+1,...,R] 可以合并成 a[L,...R] > l；

AC代码：

 #include<bits/stdc++.h>

 using namespace std;

 #define ll long long

 const int maxn=1e5+;

 int n,m,l;

 ll a[maxn];

 int fa[maxn];///a[L,...,x] > l 的最小的L；

 /**

     _bit[0][x]:a[x] > l,_bit[0][x]=1,反之为0；

     _bit[1][x]:a[L,...,R] > l,_bit[L]=1,_bit[L+1,...,R]=0，

     即满足条件的连续片段[L,...R],只将开始位置L赋为1

 */

 bitset<maxn>_bit[];

 int Find(int x)

 {

     return x == fa[x] ? x:fa[x]=Find(fa[x]);

 }

 void Solve()

 {

     for(int i=;i <= n;++i)

     {

         if(a[i] <= l)

             continue;

         _bit[].set(i);

         int x=i;

         if(_bit[][i-])

             x=Find(i-);

         fa[i]=x;

         _bit[].set(x);

     }

     for(int i=;i <= m;++i)

     {

         int que;

         scanf("%d",&que);

         if(!que)

             printf("%d\n",_bit[].count());

         else

         {

             int p,d;

             scanf("%d%d",&p,&d);

             if(_bit[][p])

                 continue;

             a[p] += d;

             if(a[p] <= l)

                 continue;

             _bit[].set(p);

             int x=p;

             if(_bit[][p-])

                 x=Find(p-);///查找a[L,...,p]>l的最小的L;

             fa[p]=x;

             ///[L,...,R]

             ///查找最大的R

             for(int j=p+;_bit[][j];++j)///每个数顶多遍历两边

             {

                 fa[j]=x;///合并[L,...,R]到x上

                 _bit[][j]=;

             }

             _bit[].set(x);

         }

     }

 }

 int main()

 {

     scanf("%d%d%d",&n,&m,&l);

     for(int i=;i <= n;++i)

     {

         fa[i]=i;

         scanf("%lld",a+i);

     }

     Solve();

     return ;

 }

ac后看了一下standings，看到了 tourist ，然后，偷偷%了一眼大神的代码；

啊，简洁+高效，tql；

AC代码：

 #include<bits/stdc++.h>

 using namespace std;

 #define ll long long

 const int maxn=1e5+;

 int n,m,l;

 ll a[maxn];

 void Solve()

 {

     int ans=;

     for(int i=;i <= n;++i)

         if(a[i] > l && a[i-] <= l)///[L,..,R]只在L处使得ans+1

             ans++;

     for(int i=;i <= m;++i)

     {

         int que;

         scanf("%d",&que);

         if(!que)

             printf("%d\n",ans);

         else

         {

             int p,d;

             scanf("%d%d",&p,&d);

             if(a[p] > l)

                 continue;

             a[p] += d;

             ///[L,..,R]只在L处使得ans+1

             if(a[p] > l && a[p-] <= l)

                 ans++;

             ///如果p使得[L,...,p-1]与[p+1,...,R]合并

             ///[L,...,p-1]使得ans+1,[p+1,...,R]使得ans+1

             ///所以ans需-1

             if(a[p] > l && a[p+] > l)

                 ans--;

         }

     }

 }

 int main()

 {

     scanf("%d%d%d",&n,&m,&l);

     for(int i=;i <= n;++i)

         scanf("%lld",a+i);

     Solve();

     return ;

 }