会修修的莫队--BZOJ2120: 数颜色

$n \leq 10000$的数列，$m \leq 10000$个操作，一：单点修改；二：查区间不同数字个数。修改数$\leq 1000$，数字$\leq 1000000$。

我不会告诉您这是三种写法的双倍经验题！！

一般可以把查区间不同个数改成：$pre_i$表示$i$之前的一个与她相同的数在哪，然后变成查某个区间$pre_i$在某个范围内的数量。可以主席树，也可分块。修改暴力重构。

方法三：带修莫队。按L块为第一关键字、R块为第二关键字、时间为第三关键字对询问排序，这样时间指针的移动复杂度是块数量的平方乘修改数。

理论上块大小取$n^{\frac{2}{3}}$是最好的，但是注意一下修改数只有1000。。于是求个导画个图象（用电脑）可得块大小280左右时最优。加了个离散化跑得飞起。

 //#include<iostream>

 #include<cstring>

 #include<cstdlib>

 #include<cstdio>

 //#include<queue>

 //#include<time.h>

 //#include<complex>

 #include<algorithm>

 #include<stdlib.h>

 using namespace std;

 int n,m,lq,lc,tot;

 #define maxn 10011

 #define maxm 288

 int a[maxn],bel[maxn];

 struct Ques{int l,r,t,id;}q[maxn];

 bool cmp(const Ques a,const Ques b) {return bel[a.l]==bel[b.l]?(bel[a.r]==bel[b.r]?a.t<b.t:a.r<b.r):a.l<b.l;}

 struct Modi{int x,a,b;}mo[maxn];

 int lisa[maxn<<],li;

 int ss; int cnt[maxn<<],ans[maxn];

 void modify(int p,int type) {cnt[a[p]]+=type; if (type>) ss+=cnt[a[p]]==; else ss-=cnt[a[p]]==;}

 void timemodify(int L,int R,int p,int v) {if (L<=p && p<=R) modify(p,-); a[p]=v; if (L<=p && p<=R) modify(p,);}

 int main()

 {

     scanf("%d%d",&n,&lq); m=;

     for (int i=;i<=n;i++) bel[i]=(i-)/m+; tot=bel[n];

     for (int i=;i<=n;i++) scanf("%d",&a[i]),lisa[++li]=a[i];

     char c; lc=;

     for (int i=,j=;i<=lq;i++)

     {

         while ((c=getchar())!='R' && c!='Q');

         if (c=='Q')

         {

             j++; scanf("%d%d",&q[j].l,&q[j].r);

             q[j].id=j; q[j].t=lc;

         }

         else

         {

             lc++; scanf("%d%d",&mo[lc].x,&mo[lc].b);

             mo[lc].a=a[mo[lc].x]; a[mo[lc].x]=mo[lc].b; lisa[++li]=mo[lc].b;

         }

     }

     lq-=lc;

     sort(lisa+,lisa++li); li=unique(lisa+,lisa++li)-lisa-;

     for (int i=;i<=n;i++) a[i]=lower_bound(lisa+,lisa++li,a[i])-lisa;

     for (int i=;i<=lc;i++) mo[i].a=lower_bound(lisa+,lisa++li,mo[i].a)-lisa,

     mo[i].b=lower_bound(lisa+,lisa++li,mo[i].b)-lisa;

     sort(q+,q++lq,cmp);

     int L=,R=,T=lc; ss=;

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

     {

         while (T>q[i].t) timemodify(L,R,mo[T].x,mo[T].a),T--;

         while (T<q[i].t) T++,timemodify(L,R,mo[T].x,mo[T].b);

         while (L<q[i].l) modify(L,-),L++;

         while (L>q[i].l) modify(L-,),L--;

         while (R<q[i].r) modify(R+,),R++;

         while (R>q[i].r) modify(R,-),R--;

         ans[q[i].id]=ss;

     }

     for (int i=;i<=lq;i++) printf("%d\n",ans[i]);

     return ;

 }

巴特西

会修修的莫队--BZOJ2120: 数颜色

最新文章

热门文章