bzoj2743离线+树状数组

时间：2020-12-25 04:22:17

奇葩染色，对于每一个点关心的是前前个同颜色的位置，但是处理方法相同

离线比较神奇，按照右端点排序，然后每次用的是左端点，就不用建可持久化树状数组（什么鬼）了

区间修改+单点查询

果断差分以后用树状数组

 #include <cstdio>

 #include <algorithm>

 struct que

 {

     int l,r,id;

 } q[];

 bool operator<(que a,que b){return a.r<b.r;}

 int n,l[],an,c,m,o[],pre[],co[],ans[];

 void add(int a,int b)

 {

     while(a<=n)

         l[a]+=b,a+=a&-a;

 }

 int get(int a)

 {

     for(an=;a;a-=a&-a)

         an+=l[a];

     return an;

 }

 int main()

 {

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

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

         scanf("%d",&o[i]),pre[i]=co[o[i]],co[o[i]]=i;

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

         scanf("%d%d",&q[i].l,&q[i].r),q[i].id=i;

     std::sort(q+,q+m+);

     int rnow=;

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

     {

         while(rnow<q[i].r)

             if(pre[++rnow]>)

                 add(pre[pre[rnow]]+,),add(pre[rnow]+,-);

         ans[q[i].id]=get(q[i].l);

     }

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

         printf("%d\n",ans[i]);

     return ;

 }

一A，开心

树状数组好久不写居然写对了

相关文章