丢板子还需要别的内容吗

题目参见数颜色

#include<cstdio>
#include<iostream>
#include<cstring>
#include<string>
#include<cmath>
#include<cstdlib>
#include<algorithm>
#include<iterator>
using namespace std;

struct asksx
{
    int leftx,rightx,mod_time;
    int ansx,codex;
}ask[10010]={0};
struct modifies
{
    int pos,val;
}modi[10010]={0};
int n,m,seq[10010]={0},modtime=0,blksz=0;
int ctr1=0,ctr2=0,lpos=0,rpos=0,anss=0;
char ch=0;
int exi[1000010]={0},belong[10010]={0};

inline void readx(int& x)
{
    x=0; int k=1; register char ch=0;
    while (ch<'0' || ch>'9') { ch=getchar(); if (ch=='-') k=-1; }
    while (ch>='0' && ch<='9') { x=x*10+ch-'0'; ch=getchar(); }
    x*=k;
}

inline bool cmp1(asksx a,asksx b)
{
    if (belong[a.leftx]==belong[b.leftx])
    {
        if (belong[a.rightx]==belong[b.rightx]) return a.mod_time<b.mod_time;
        return belong[a.rightx]<belong[b.rightx];
    }
    return belong[a.leftx]<belong[b.leftx];
}
inline bool cmp2(asksx a,asksx b) { return a.codex<b.codex; }

inline void process1(int i)
{
    if (modi[modtime].pos>=lpos && modi[modtime].pos<=rpos)
    {
        exi[seq[modi[modtime].pos]]--;
        exi[modi[modtime].val]++;
        if (exi[seq[modi[modtime].pos]]==0) anss--;
        if (exi[modi[modtime].val]==1) anss++;
    }
}

int main()
{
    readx(n); readx(m); blksz=sqrt(n);
    for (int i=1;i<=n;i++) belong[i]=(i/blksz)+1;
    for (int i=1;i<=n;i++) readx(seq[i]);
    for (int i=1;i<=m;i++)
    {
        ch=0; while (ch<'A' || ch>'Z') ch=getchar();
        if (ch=='Q')
        {
            ctr1++; readx(ask[ctr1].leftx); readx(ask[ctr1].rightx);
            ask[ctr1].mod_time=modtime; ask[ctr1].codex=ctr1;
        }
        else
        {
            modtime++; ctr2++;
            readx(modi[ctr2].pos); readx(modi[ctr2].val);
        }
    }
    
    modtime=0; sort(ask+1,ask+ctr1+1,cmp1); lpos=rpos=0;
    for (int i=1;i<=ctr1;i++)
    {
        while (ask[i].mod_time>modtime)
        {
            modtime++;
            process1(i); swap(seq[modi[modtime].pos],modi[modtime].val);
        }
        while (ask[i].mod_time<modtime)
        {
            process1(i); swap(seq[modi[modtime].pos],modi[modtime].val);
            modtime--;
        }
        while (rpos>ask[i].rightx)
        {
            exi[seq[rpos]]--; if (exi[seq[rpos]]==0) anss--;
            rpos--;
        }
        while (rpos<ask[i].rightx)
        {
            rpos++;
            exi[seq[rpos]]++; if (exi[seq[rpos]]==1) anss++;
        }
        while (lpos<ask[i].leftx)
        {
            exi[seq[lpos]]--; if (exi[seq[lpos]]==0) anss--;
            lpos++;
        }
        while (lpos>ask[i].leftx)
        {
            lpos--;
            exi[seq[lpos]]++; if (exi[seq[lpos]]==1) anss++;
        }
        ask[i].ansx=anss;
    }
    
    sort(ask+1,ask+ctr1+1,cmp2);
    for (int i=1;i<=ctr1;i++) printf("%d\n",ask[i].ansx);
    return 0;
}

发表评论

电子邮件地址不会被公开。 必填项已用*标注

This site uses Akismet to reduce spam. Learn how your comment data is processed.