F.A.Qs Home ProblemSet Status Ranklist Contest LoginRegister
Notice:祝各位Oier新年快乐,Rp++!
大视野在线测评-欢迎您
[ New Thread ]
Problem 2453 >> luoguAC bzojRE
XTYF_CKY @ 2018-01-22 11:40:13
[ Quote ] [ Edit ] [ Delete ] 1#
#include <cstdio>
#include <algorithm>
#include <cmath>
#include <iostream>
using namespace std;
int n,m,col[10005],vis[1000005],nowl,nowr,nowm,cnt,divide,ans[10005],x,y,cur,col2[10005];
char typ[10005];
struct mo
{
int l,r,id,block,update;
mo(int l=0,int r=0,int id=0,int block=0,int update=0):l(l),r(r),id(id),block(block),update(update){}
}q[10005];
struct nod
{
int num,bf,af;
nod(int num=0,int bf=0,int af=0):num(num),bf(bf),af(af){}
}modify[1005];
bool cmp(mo a,mo b)
{
if(a.block!=b.block)
return a.block<b.block;
if(a.r!=b.r)
return a.r<b.r;
if(a.update!=b.update)
return a.update<b.update;
}
int main()
{
scanf("%d%d",&n,&m);
divide=pow(n,2.0/3.0);
for(int i=1;i<=n;i++)
{
scanf("%d",&col[i]);
col2[i]=col[i];
}
for(int i=1;i<=m;i++)
{
cin>>typ[i];
scanf("%d%d",&x,&y);
if(typ[i]=='Q')
q[i]=mo(x,y,i,x/divide+1,cur);
if(typ[i]=='R')
{
q[i]=mo(0,0,i,2147483647,0);
cur++;
modify[cur]=nod(x,col2[x],y);
col2[x]=y;
}
}
sort(q+1,q+m+1,cmp);
for(int i=1;i<=m;i++)
{
if(q[i].block>1000)
break;
while(nowm>q[i].update)
{
if(nowl<=modify[nowm].num&&nowr>=modify[nowm].num)//如果被修改的点在当前区间内要更新答案
{
vis[col[modify[nowm].num]]--;
if(!vis[col[modify[nowm].num]])
cnt--;
}
col[modify[nowm].num]=modify[nowm].bf;
if(nowl<=modify[nowm].num&&nowr>=modify[nowm].num)//修改前的减答案,修改后的加答案
{
vis[col[modify[nowm].num]]++;
if(vis[col[modify[nowm].num]]==1)
cnt++;
}
nowm--;
}
while(nowm<q[i].update)
{
nowm++;//直接进行下一次修改,并且最后一次修改也要保证
if(nowl<=modify[nowm].num&&nowr>=modify[nowm].num)
{
vis[col[modify[nowm].num]]--;
if(!vis[col[modify[nowm].num]])
cnt--;
}
col[modify[nowm].num]=modify[nowm].af;
if(nowl<=modify[nowm].num&&nowr>=modify[nowm].num)
{
vis[col[modify[nowm].num]]++;
if(vis[col[modify[nowm].num]]==1)
cnt++;
}
}
while(nowl<q[i].l)
{//减答案要减当前节点,所以指针移动在后面,加答案不算当前节点但是要算最后的节点,所以指针移动在前面
vis[col[nowl]]--;
if(!vis[col[nowl]])
cnt--;
nowl++;
}
while(nowl>q[i].l)
{
nowl--;
vis[col[nowl]]++;
if(vis[col[nowl]]==1)
cnt++;
}
while(nowr<q[i].r)
{
nowr++;
vis[col[nowr]]++;
if(vis[col[nowr]]==1)
cnt++;
}
while(nowr>q[i].r)
{
vis[col[nowr]]--;
if(!vis[col[nowr]])
cnt--;
nowr--;
}
if(typ[q[i].id]=='Q')
ans[q[i].id]=cnt;
}
for(int i=1;i<=m;i++)
if(typ[i]=='Q')
printf("%d\n",ans[i]);
}
nzhtl1477 @ 2018-01-22 11:53:41
[ Quote ] [ Edit ] [ Delete ] 2#
女装吧
iloi @ 2018-01-22 13:48:12
[ Quote ] [ Edit ] [ Delete ] 3#
女装吧。@nzhtl1477 可以教你
Cydiater @ 2018-01-22 17:46:47
[ Quote ] [ Edit ] [ Delete ] 4#
REOJ
lijiamu @ 2018-01-22 21:19:18
[ Quote ] [ Edit ] [ Delete ] 5#
女装吧
Leohh @ 2018-01-22 21:19:59
[ Quote ] [ Edit ] [ Delete ] 6#
女装吧
ranwan @ 2018-01-22 21:20:47
[ Quote ] [ Edit ] [ Delete ] 7#
女装吧
this_problem_is_bad @ 2018-01-22 21:21:15
[ Quote ] [ Edit ] [ Delete ] 8#
女装吧
XTYF_CKY @ 2018-01-22 21:46:01
[ Quote ] [ Edit ] [ Delete ] 9#
%%%zrxjulao
iloi @ 2018-01-22 22:41:29
[ Quote ] [ Edit ] [ Delete ] 10#
%%%zrxjulao
fxj885 @ 2018-01-23 07:23:04
[ Quote ] [ Edit ] [ Delete ] 11#
女装吧
[Top] [Previous Page] [Next Page]

HOME Back