【NOIシミュレーション】メンテナンスキュー
Description
子供の頃パチンコをしたことがありますか.子供Aはいくつかの弾珠があって、Aはそれらを列に並ぶのが好きで、左から右まで1からNに番号をつけます.列全体が鮮やかで美しいために、子供はある連続弾珠の中で、異なる色の弾珠がどれだけあるか知りたいと思っています.もちろん、Aは個人の好みに応じて、キューの中の弾珠の色を置き換えることがあります.しかしAはまだプログラミングを習ったことがなく、頭の嵐が脳力を浪費していると思っているので、助けを求めています.
Solution
修正待ちのチームアルゴリズム、裸!修正された莫隊アルゴリズムには原題【uva 12345】Dynamic lenがある
Code
子供の頃パチンコをしたことがありますか.子供Aはいくつかの弾珠があって、Aはそれらを列に並ぶのが好きで、左から右まで1からNに番号をつけます.列全体が鮮やかで美しいために、子供はある連続弾珠の中で、異なる色の弾珠がどれだけあるか知りたいと思っています.もちろん、Aは個人の好みに応じて、キューの中の弾珠の色を置き換えることがあります.しかしAはまだプログラミングを習ったことがなく、頭の嵐が脳力を浪費していると思っているので、助けを求めています.
Solution
修正待ちのチームアルゴリズム、裸!修正された莫隊アルゴリズムには原題【uva 12345】Dynamic lenがある
Code
#include
#include
#include
#include
#include
#define fo(i,a,b) for(i=a;i<=b;i++)
#define fod(i,a,b) for(i=a;i>=b;i--)
using namespace std;
const int maxn=50007;
struct node{
int l,r,x,p;
}a[maxn];
struct nod{
int x,y,o;
}d[maxn];
int i,j,k,l,t,n,m,ans,now,kuai[maxn],da,last[maxn],tot,num,r;
bool bz[maxn];
int shu[1000007],b[maxn],ans1[maxn];
char s[10];
bool cmp(node x,node y){
return kuai[x.l]void update(int x){
if(bz[x]){
shu[b[x]]--;
if(!shu[b[x]])ans--;
}
else{
shu[b[x]]++;
if(shu[b[x]]==1)ans++;
}
bz[x]^=1;
}
void change(int x,int y){
if(bz[x]){
update(x);b[x]=y;update(x);
}
else b[x]=y;
}
int main(){
//freopen("fan.in","r",stdin);
//freopen("fan.out","w",stdout);
scanf("%d%d",&n,&m);
da=500;
fo(i,1,n)scanf("%d",&b[i]),kuai[i]=i/da,last[i]=b[i];
fo(i,1,m) {
scanf("%s%d%d",s,&k,&l);
if (s[0]=='Q')a[++tot].l=k,a[tot].r=l,a[tot].x=num,a[tot].p=tot;
else d[++num].x=k,d[num].o=last[k],d[num].y=l,last[k]=l;
}
sort(a+1,a+1+tot,cmp);
l=1;
fo(i,1,tot){
if (now1,a[i].x)change(d[j].x,d[j].y);
else fod(j,now,a[i].x+1)change(d[j].x,d[j].o);
if (l1)update(j);
else fo(j,a[i].l,l-1)update(j);
if (r1,a[i].r)update(j);
else fo(j,a[i].r+1,r)update(j);
ans1[a[i].p]=ans;l=a[i].l;r=a[i].r;now=a[i].x;
}
fo(i,1,tot)printf("%d",ans1[i]);
}