待修改的莫队 洛谷P1903 [国家集训队] 数颜色 / 维护队列

最坑的是输入除了'Q','R'还有其他字母；

 1 #include
 2 using namespace std;
 3 typedef long long ll; 
 4 const int N=1e6+5;
 5 int color[N],blg[N],cnt[N],ans[N];
 6 int n,m,tot,qcnt,tcnt;
 7 inline int read()
 8 {
 9     int x=0,f=1;char ch=getchar();
10     while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();}
11     while(ch>='0'&&ch<='9'){x=(x<<1)+(x<<3)+(ch^48);ch=getchar();}
12     return x*f;
13 }
14 struct event{
15     int l,r,pos,t;
16 }e[N];
17 static bool cmp(event &a,event &b)
18 {
19     return (blg[a.l]^blg[b.l])?blg[a.l]b.t);
20 }
21 
22 struct change
23 {
24     int id,cl;
25 }cg[N];
26 void del(int pos)
27 {
28     if(!(--cnt[color[pos]]))--tot;
29 }
30 void add(int pos)
31 {
32     if((++cnt[color[pos]])==1)tot++;
33 }
34 void update(int t,int ql,int qr)
35 {
36 
37     int id=cg[t].id,col=cg[t].cl;
38     if(ql<=id&&id<=qr)
39     {
40         if(!(--cnt[color[id]]))--tot;
41         if((++cnt[col])==1)tot++;
42     }
43     swap(color[id],cg[t].cl);
44 }
45 int main()
46 {
47     n=read();m=read();
48     for(int i=1;i<=n;i++)color[i]=read();
49     int sz=ceil(pow(n,2.0/3.0));
50     for(int i=1;i<=n;i++)blg[i]=(i-1)/sz+1;
51     for(int i=1;i<=m;i++)
52     {
53         char op[3];
54         scanf("%s",op);
55         if(op[0]=='Q')
56         {
57             int ql=read(),qr=read();
58             e[++qcnt].l=ql;e[qcnt].r=qr;
59             e[qcnt].pos=qcnt;e[qcnt].t=tcnt;
60         }
61         else if(op[0]=='R')
62         {
63             int id=read(),col=read();
64             cg[++tcnt].id=id,cg[tcnt].cl=col;
65         }
66     }
67     sort(e+1,e+1+qcnt,cmp);
68     int l=1,r=0,t=0;
69     for(int i=1;i<=qcnt;i++)
70     {
71         int ql=e[i].l,qr=e[i].r,qt=e[i].t;
72         while(l);
73         while(l>ql)add(--l);
74         while(rr);
75         while(r>qr)del(r--);
76         while(tt,ql,qr);
77         while(t>qt)update(t--,ql,qr);
78         ans[e[i].pos]=tot;
79     }
80     for(int i=1;i<=qcnt;i++)printf("%d\n",ans[i]);
81     return 0;
82 }