人 傻 常 数 大
查看原帖
人 傻 常 数 大
160839
Prean楼主2020/5/9 23:22

后面6个全T了,求帮忙卡常QwQ

Code:

#include<algorithm>
#include<iostream>
#include<cmath>
const int M=1e6+5;
int n,m,L,R,now,ans,cnt1,cnt2;
int a[M],qwq[M],pst[M],val[M],color[M];
struct sec
{
    int L,R,t,bl,num;
    friend bool operator<(const sec&a,const sec&b)
    {
        return a.bl==b.bl?a.R<b.R:a.L<b.L;
    }
}s[M];
inline void swap(int&x,int&y){x^=y^=x^=y;}
inline void Add(int v){if(++a[v]==1)++ans;}
inline void Del(int v){if(--a[v]==0)--ans;}
inline void Wrk(int v)
{
    if(L<=pst[v]&&pst[v]<=R)Del(color[pst[v]]),Add(val[v]);
    swap(color[pst[v]],val[v]);
}
inline int read()
{
    char s;int f=1,n=0;while(!isdigit(s=getchar()))if(s==45)f=-1;
    while(n=n*10+(s^48),isdigit(s=getchar()));return f*n;
}
inline void write(int n)
{
    char s[105];int top=0;while(s[++top]=n%10+'0',n/=10);
    while(putchar(s[top--]),top);
}
signed main()
{
    n=read();m=read();
    int i,p=sqrt(n);
    for(i=1;i<=n;++i)color[i]=read();
    for(i=1;i<=m;++i)
    {
        char ch;
        std::cin>>ch;
        if(ch=='Q')
        {
            s[++cnt1].num=cnt1;
            s[cnt1].L=read();s[cnt1].R=read();
            s[cnt1].bl=s[cnt1].L/p;s[cnt1].t=cnt2;
        }
        if(ch=='R')
        {
            ++cnt2;
            pst[cnt2]=read();val[cnt2]=read();
        }
    }
    std::sort(s+1,s+cnt1+1);
    for(i=1;i<=cnt1;++i)
    {
        int l=s[i].L,r=s[i].R;
        while(L<l)Del(color[L++]);
        while(R<r)Add(color[++R]);
        while(L>l)Add(color[--L]);
        while(R>r)Del(color[R--]);
        while(now<s[i].t)Wrk(++now);
        while(now>s[i].t)Wrk(now--);
        qwq[s[i].num]=ans;
    }
    for(i=1;i<=cnt1;++i)write(qwq[i]),putchar(10);
}
2020/5/9 23:22
加载中...