【做题记录】ADAUNIQ - Ada and Unique Vegetable

link

做法：带修莫队

#include<cstdlib>
#include<cmath>
#include<cstdio>
#include<cctype>
#include<algorithm>
typedef long long LL;
typedef unsigned long long ULL;
namespace FastIo{
    typedef __uint128_t ULLL;
    static char buf[100000],*p1=buf,*p2=buf,fw[100000],*pw=fw;
    #define gc p1==p2&&(p2=(p1=buf)+fread(buf,1,100000,stdin),p1==p2)?EOF:*p1++
    inline void pc(const char &ch){
    	if(pw-fw==100000)fwrite(fw,1,100000,stdout),pw=fw;
    	*pw++=ch;
	}
    #define fsh fwrite(fw,1,pw-fw,stdout),pw=fw
	struct FastMod{
        FastMod(ULL b):b(b),m(ULL((ULLL(1)<<64)/b)){}
        ULL reduce(ULL a){
            ULL q=(ULL)((ULLL(m)*a)>>64);
            ULL r=a-q*b;
            return r>=b?r-b:r;
        }
        ULL b,m;
    }HPOP(10);
    struct QIO{
    	char ch;
    	int st[40];
    	inline void read(int &x){
    		x=0,ch=gc;
    		while(!isdigit(ch))ch=gc;
    		while(isdigit(ch)){x=(x<<3)+(x<<1)+(ch^48);ch=gc;}
		}
		inline void write(int a){
			do{st[++st[0]]=HPOP.reduce(a);a/=10;}while(a);
			while(st[0])pc(st[st[0]--]^48);
			pc('\n');
		}
	}qrw;
}
using namespace FastIo;
#define NUMBER1 1000000
#define P(A) A=-~A
#define fione_i(begin,end) for(register int i=begin;i<=end;P(i))
int n,m,a[NUMBER1+5],ans[NUMBER1+5],mq(0),mc(0),fk,sum(0),cnt[NUMBER1+5];
struct ASK{
	int id,l,r,t;
	bool operator<(const ASK &A)const{
		int L=l/fk,AL=A.l/fk,R=r/fk,AR=A.r/fk;
		return (L!=AL)?(L<AL):((R!=AR)?(R<AR):(t<A.t));
	}
	ASK(int id=0,int l=0,int r=0,int t=0):id(id),l(l),r(r),t(t){}
}q[NUMBER1+5];
struct CHANGE{
	int p,color;
	CHANGE(int p=0,int color=0):p(p),color(color){}
}c[NUMBER1+5];
inline void add(const int &data){
	P(cnt[data]);
	if(cnt[data]==1)P(sum);
	else if(cnt[data]==2)--sum;
}
inline void del(const int &data){
	--cnt[data];
	if(!cnt[data])--sum;
	else if(cnt[data]==1)P(sum);
}
signed main(){
	int x,y,t(0),op;
	qrw.read(n);
	qrw.read(m);
	fione_i(1,n)qrw.read(a[i]);
	fione_i(1,m){
		qrw.read(op);
		qrw.read(x);
		qrw.read(y);
		if(op==2)mq++,q[mq]=ASK(mq,x+1,y+1,mc);
		else c[++mc]=CHANGE(x+1,y);
	}
	fk=pow((double)n*std::max(1,mc),1.0/3),x=1,y=0;
	std::sort(q+1,q+1+mq);
	fione_i(1,mq){
		while(y<q[i].r)add(a[++y]);
		while(y>q[i].r)del(a[y--]);
		while(x<q[i].l)del(a[x++]);
		while(x>q[i].l)add(a[--x]);
		while(t<q[i].t){
			P(t);
			if(c[t].p<=y&&c[t].p>=x){
				del(a[c[t].p]);
				add(c[t].color);
			}
			std::swap(a[c[t].p],c[t].color);
		}
		while(t>q[i].t){
			if(c[t].p<=y&&c[t].p>=x){
				del(a[c[t].p]);
				add(c[t].color);
			}
			std::swap(a[c[t].p],c[t].color);
			--t;
		}
		ans[q[i].id]=sum;
	}
	fione_i(1,mq)qrw.write(ans[i]);
	fsh;
    exit(0);
    return 0;
}