看心情填坑

和lnj还有炼哥口胡BZOJ3236之后

感觉这一类什么主席树强制在线维护区间颜色数的题好像有很多，感觉学会就能A很多题，非常excing干脆开个坑

这一类问题离线可以莫队+分块乱搞，但是在线就需要主席树+特殊的黑科技

2120、3236、4026、2453、3809不要吐槽双倍经验题

4026

题意：求区间乘积的欧拉函数，强制在线，%一个大素数

看hzw博客然后转到PoPoQQQ被PoPoQQQ剧透一脸_(:зゝ∠)_

因为a_i<=100W，所以我们可以把每一个数拆成不超过7个素数，变成35W的一个序列，然后前缀积逆元。

主席树查询一下区间出现过的素数的(p_i-1)/p_i就可以了

一开始还以为被卡常然后发现是自己输出调试没有删。。。

#include<cstdio>
#define mo 1000777
using namespace std;
int	l[50005],r[50005],ine[mo],col[50005];
int a[350005],next[350005],last[1000005];
int rt[350005];
int prime[169]={2,3,5,7,11,13,17,19,23,29,31,37,41,43,47,53,59,61,67,71,73,79,83,89,97,101,103,107,109,113,127,131,137,139,149,151,157,163,167,173,179,181,191,193,197,199,211,223,227,229,233,239,241,251,257,263,269,271,277,281,283,293,307,311,313,317,331,337,347,349,353,359,367,373,379,383,389,397,401,409,419,421,431,433,439,443,449,457,461,463,467,479,487,491,499,503,509,521,523,541,547,557,563,569,571,577,587,593,599,601,607,613,617,619,631,641,643,647,653,659,661,673,677,683,691,701,709,719,727,733,739,743,751,757,761,769,773,787,797,809,811,821,823,827,829,839,853,857,859,863,877,881,883,887,907,911,919,929,937,941,947,953,967,971,977,983,991,997,1009};
struct tree{
	int l,r,w;
}t[3200000];
inline int read(){
    int ret=0;
    char c=getchar();
    while((c>'9')||(c<'0'))c=getchar();
    while((c>='0')&&(c<='9'))ret=(ret<<1)+(ret<<3)+c-'0',c=getchar();
    return ret;
}
int n,m,cnt,ans;
inline int pow(int x,int k){
	int ans=1;
	for(;k;k>>=1,x=1LL*x*x%mo)if(k&1)ans=1LL*ans*x%mo;
	return ans;
}
inline int Ine(int x){
	if(!ine[x])ine[x]=pow(x,mo-2);
	return ine[x];
}
#define mid (l+r>>1)
void build(int l,int r,int root){
	t[root].w=1;
	if(l==r)return;
	t[root].l=++cnt;
	build(l,mid,t[root].l);
	t[root].r=++cnt;
	build(mid+1,r,t[root].r);
}
void change(int l,int r,int k,int Root,int root){
	t[root].w=1LL*t[Root].w*(a[k]-1)%mo*Ine(a[k])%mo;
	if(l==r)return;
	if(next[k]<=mid){
		t[root].l=++cnt;
		t[root].r=t[Root].r;
		change(l,mid,k,t[Root].l,t[root].l);
	}else{
		t[root].l=t[Root].l;
		t[root].r=++cnt;
		change(mid+1,r,k,t[Root].r,t[root].r);
	}
}
inline int query(int k,int l,int r,int Root,int root){
//	printf("%d %d %d %d %d\n",k,l,r,Root,root);
	if(k==l)return 1LL*t[root].w*Ine(t[Root].w)%mo;
	if(k>mid)return query(k,mid+1,r,t[Root].r,t[root].r);
	else return 1LL*query(k,l,mid,t[Root].l,t[root].l)*t[t[root].r].w%mo*Ine(t[t[Root].r].w)%mo;
}
int main(){
	n=read();m=read();
	col[0]=1;
	for(int i=1;i<=n;i++){
		int x=read();
		col[i]=1LL*col[i-1]*x%mo;
		l[i]=cnt+1;
		for(int i=0;prime[i]*prime[i]<=x;i++)if(x%prime[i]==0){
			cnt++;a[cnt]=prime[i];
			while(x%prime[i]==0)x/=prime[i];
		}
		if(x>1){cnt++;a[cnt]=x;}
		r[i]=cnt;
	}
	n=cnt;
	for(int i=n;i;i--){
		if(last[a[i]])next[i]=last[a[i]];
		else next[i]=n+1;
		last[a[i]]=i;
	}
	cnt=1;rt[0]=1;
	build(1,n+1,1);
	for(int i=1;i<=n;i++){
		rt[i]=++cnt;
		change(1,n+1,i,rt[i-1],rt[i]);
	}
//	for(int i=1;i<=n;i++)printf("%d %d\n",a[i],next[i]);
//	puts("");
	while(m--){
		int L=read(),R=read();
		L^=ans;R^=ans;
		ans=1LL*col[R]*Ine(col[L-1])%mo;
		L=l[L];R=r[R];
//		printf("%d %d %d\n",L,R,ans);
		ans=1LL*ans*query(R+1,1,n+1,rt[L-1],rt[R])%mo;
		printf("%d\n",ans);
	}
}

3236

可以莫队，CDQ，树套树，我打算都写一下。

先说树套树和CDQ，

我们把位置，颜色，ntrnext数组作为三维坐标，问题就是求一个范围内的点的数量。

这个东西显然满足区间相减，所以我们可以排序降一维，还有两维

强制在线的话可以选择树状数组套线段树，直接两维。允许离线的话可以选择空间小而且容易调的CDQ,$O((n+m)log^{2})$,orzxyz

然后是莫队

莫队因为它的延续性所以只有位置+颜色两维，next数组的限制我们可以中间记录颜色有几个来维护。

然后数据结构弄掉一维之后就是莫队，和分块结合可以\(O((n+m)\sqrt{n})\)

MDZZ写法:树状数组套主席树(可持久化又不支持修改有卵用，不如直接线段树)，莫队套树状数组(O(nlogn*sqrt(n)+mlog(n)))

我打算都写一下。

RE到死最后发现自己把M看成了10W....

#include<cstdio>
#include<algorithm>
using namespace std;
struct query{
    int x,yl,yr,z,v,p;
}q[2000005],qtmp1[2000005],qtmp2[2000005];
struct work{
    int x,y,z;
}w[100005],wtmp1[100005],wtmp2[100005];
int n,m,cnt;
int head[100005],ans1[1000005],ans2[1000005],tree[100005];
bool cmp(query k1,query k2){return k1.x<k2.x;}
inline int lowbit(int k){return k&-k;}
inline void add(int k,int x){while(k<=n){tree[k]+=x;k+=lowbit(k);}}
inline int sum(int k){int ans=0;while(k){ans+=tree[k];k-=lowbit(k);}return ans;}
inline int read(){
    int ret=0;
    char c=getchar();
    while((c>'9')||(c<'0'))c=getchar();
    while((c>='0')&&(c<='9'))ret=(ret<<1)+(ret<<3)+c-'0',c=getchar();
    return ret;
}
inline void cdq(int l,int r,int wl,int wr,int ql,int qr){
    if(l==r)return;
    int mid=(l+r)>>1,k=wl,wcnt1=0,wcnt2=0,qcnt1=0,qcnt2=0;
    for(int i=ql;i<=qr;i++){
        while((w[k].x<=q[i].x)&&(k<=wr)){
            if(w[k].z<=mid){
                add(w[k].y,1);
                wtmp1[++wcnt1]=w[k];
            }else wtmp2[++wcnt2]=w[k];
            k++;
        }
        if(k==wl)continue;
        if(q[i].z>mid){
            ans2[q[i].p]+=q[i].v*(sum(q[i].yr)-sum(q[i].yl-1));
            qtmp2[++qcnt2]=q[i];
        }else qtmp1[++qcnt1]=q[i];
    }
    for(int i=1;i<=wcnt1;i++){add(wtmp1[i].y,-1);w[wl+i-1]=wtmp1[i];}
    for(int i=1;i<=wcnt2;i++)w[wl+wcnt1+i-1]=wtmp2[i];
    if(wcnt1)for(int i=1;i<=qcnt1;i++)q[ql+i-1]=qtmp1[i];
    if(wcnt2)for(int i=1;i<=qcnt2;i++)q[ql+qcnt1+i-1]=qtmp2[i];
    if((wcnt1)&&(qcnt1))cdq(l,mid,wl,wl+wcnt1-1,ql,ql+qcnt1-1);
    if((wcnt2)&&(qcnt2))cdq(mid+1,r,wl+wcnt1,wr,ql+qcnt1,ql+qcnt1+qcnt2-1);
}
int main(){
    n=read();m=read();
    for(int i=1;i<=n;i++){
        int x=read();
        w[i]=(work){i,x,head[x]};
        head[x]=i;
    }
    for(int i=1;i<=m;i++){
        int l=read(),r=read(),L=read(),R=read();
        if(l>1)q[++cnt]=(query){l-1,L,R,l,-1,i};
        q[++cnt]=(query){r,L,R,l,1,i};
    }
    sort(q+1,q+1+cnt,cmp);
    int k=1;
    for(int i=1;i<=cnt;i++){
        while((w[k].x<=q[i].x)&&(k<=n))add(w[k++].y,1);
        ans1[q[i].p]+=q[i].v*(sum(q[i].yr)-sum(q[i].yl-1));
    }
    for(int i=1;i<=n;i++)tree[i]=0;
    cdq(0,n,1,n,1,cnt);
    for(int i=1;i<=m;i++)printf("%d %d\n",ans1[i],ans2[i]);
}

#include<cstdio>
#include<algorithm>
using namespace std;
inline int read(){
    int ret=0;
    char c=getchar();
    while((c>'9')||(c<'0'))c=getchar();
    while((c>='0')&&(c<='9'))ret=(ret<<1)+(ret<<3)+c-'0',c=getchar();
    return ret;
}
int n,m,cnt,acnt,tcnt;
int head[100005],ans1[1000005],ans2[1000005];
struct work{
    int x,y,z;
}w[100005];
struct query{
    int x,yl,yr,zr,v,p;
}q[2000005];
struct tree{
    int l,r,s;
}t[39000000],a[400005];
inline bool wcmp(work k1,work k2){return k1.x<k2.x;}
inline bool qcmp(query q1,query q2){return q1.x<q2.x;}
#define mid (l+r>>1)
inline int newnode(){a[++acnt]=(tree){0,0,0};return acnt;}
inline int lowbit(int k){return k&-k;}
void ins(int l,int r,int p,int now){
//  printf("l=%d r=%d p=%d now=%d\n",l,r,p,now);
    t[now].s++;
    if(l==r)return;
    if(p<=mid){
        if(!t[now].l)t[now].l=++tcnt;
        ins(l,mid,p,t[now].l);
    }else{
        if(!t[now].r)t[now].r=++tcnt;
        ins(mid+1,r,p,t[now].r);
    }
}
void Ins(int kx,int ky){while(kx<=n){ins(0,n-1,ky,kx);kx+=lowbit(kx);}}
void mer(int l,int r,int L,int R,int Rt,int rt){
    a[rt].s+=t[Rt].s;
    if((L<=l)&&(R>=r))return;
    if((L<=mid)&&(t[Rt].l)){
        if(!a[rt].l)a[rt].l=newnode();
        mer(l,mid,L,R,t[Rt].l,a[rt].l);
    }
    if((R>mid)&&(t[Rt].r)){
        if(!a[rt].r)a[rt].r=newnode();
        mer(mid+1,r,L,R,t[Rt].r,a[rt].r);
    }
}
inline int que(int l,int r,int L,int R,int rt){
    if((L<=l)&&(R>=r))return a[rt].s;
    int re=0;
    if((L<=mid)&&(a[rt].l))re+=que(l,mid,L,R,a[rt].l);
    if((R>mid)&&(a[rt].r))re+=que(mid+1,r,L,R,a[rt].r);
    return re;
}
inline int quer(int xr,int yr){
    acnt=0;newnode();
    while(xr){mer(0,n-1,0,yr,xr,1);xr-=lowbit(xr);}
    int ans=que(0,n-1,0,yr,1);
    return ans;
}
int main(){
    n=read();m=read();
    for(int i=1;i<=n;i++){
        int x=read();
        w[i]=(work){x,i,head[x]};
        head[x]=i;
    }
    sort(w+1,w+1+n,wcmp);
    for(int i=1;i<=m;i++){
        int yl=read(),yr=read(),l=read(),r=read();
        q[++cnt]=(query){l-1,yl,yr,yl-1,-1,i};
        q[++cnt]=(query){r,yl,yr,yl-1,1,i};
    }
    sort(q+1,q+1+cnt,qcmp);
    int k=1;tcnt=n;
    for(int i=1;i<=cnt;i++){
        while((k<=n)&&(w[k].x<=q[i].x)){
            Ins(w[k].y,w[k].z);
            k++;
        }
        if(!q[i].x)continue;
        ans1[q[i].p]+=q[i].v*(quer(q[i].yr,q[i].zr)-quer(q[i].yl-1,q[i].zr));
        ans2[q[i].p]+=q[i].v*(quer(q[i].yr,n-1)-quer(q[i].yl-1,n-1));
    }
  for(int i=1;i<=m;i++)printf("%d %d\n",ans2[i],ans1[i]);
}

#include<cstdio>
#include<algorithm>
#include<cmath>
using namespace std;
int size,n,m,l,r;
int block1[320],block2[320],a1[102005],a2[102005];
int a[100005],ans1[1000005],ans2[1000005];
struct query{
    int l,r,L,R,k;
}q[1000005];
bool cmp(query k1,query k2){
    if(k1.l/size!=k2.l/size)return k1.l/size<k2.l/size;
    else return k1.r<k2.r;
}
inline int read(){
    int ret=0;
    char c=getchar();
    while((c>'9')||(c<'0'))c=getchar();
    while((c>='0')&&(c<='9'))ret=(ret<<1)+(ret<<3)+c-'0',c=getchar();
    return ret;
}
void add(int k){
    a1[k]++;block1[k/size]++;
    if(a2[k]==0){
        a2[k]=1;
        block2[k/size]++;
    }
}
void dec(int k){
    a1[k]--;block1[k/size]--;
    if(a1[k]==0){
        a2[k]=0;
        block2[k/size]--;
    }
}
inline int query1(int l,int r){
    int ans=0;
    if(l/size==r/size){
        for(int i=l;i<=r;i++)ans+=a1[i];
        return ans;
    }
    for(int i=l/size+1;i<r/size;i++)ans+=block1[i];
    for(int i=l;i<(l/size+1)*size;i++)ans+=a1[i];
    for(int i=r/size*size;i<=r;i++)ans+=a1[i];
    return ans;
}
inline int query2(int l,int r){
    int ans=0;
    if(l/size==r/size){
        for(int i=l;i<=r;i++)ans+=a2[i];
        return ans;
    }
    for(int i=l/size+1;i<r/size;i++)ans+=block2[i];
    for(int i=l;i<(l/size+1)*size;i++)ans+=a2[i];
    for(int i=r/size*size;i<=r;i++)ans+=a2[i];
    return ans;
}
int main(){
    scanf("%d%d",&n,&m);
    size=int(sqrt(n)+0.00001);
    for(int i=0;i<n;i++)a[i]=read()-1;
    for(int i=1;i<=m;i++)q[i].l=read()-1,q[i].r=read()-1,q[i].L=read()-1,q[i].R=read()-1,q[i].k=i;
    sort(q+1,q+1+m,cmp);
    for(int i=q[1].l;i<=q[1].r;i++)add(a[i]);
    ans1[q[1].k]=query1(q[1].L,q[1].R);
    ans2[q[1].k]=query2(q[1].L,q[1].R);
    l=q[1].l;r=q[1].r;
    for(int i=2;i<=m;i++){
        while(l>q[i].l)add(a[--l]);
        while(r<q[i].r)add(a[++r]);
        while(l<q[i].l)dec(a[l++]);
        while(r>q[i].r)dec(a[r--]);
        ans1[q[i].k]=query1(q[i].L,q[i].R);
        ans2[q[i].k]=query2(q[i].L,q[i].R);
    }
    for(int i=1;i<=m;i++)printf("%d %d\n",ans1[i],ans2[i]);
}

从上到下依次是莫队、CDQ、树套树。空间上莫队最优，时间上CDQ最优，但是树套树能做到在线。其实是因为我CDQ卡常了其它没卡

3809

树套树和CDQ都不幸被卡了空间，然后就上莫队，又不幸被卡了常数_(:зゝ∠)_

卡评测卡了好几发终于爆过去了

#include<cstdio>
#include<algorithm>
#include<cmath>
using namespace std;
int size,n,m,l,r;
int block[320],a1[102005],belong[100005];
int a[100005],ans[1000005];
struct query{
    int l,r,L,R,k;
}q[1000005];
bool cmp(query k1,query k2){
    if(k1.l/size!=k2.l/size)return k1.l/size<k2.l/size;
    else return k1.r<k2.r;
}
void write(int x){
    int k=1;
    while((k<<1)+(k<<3)<=x)k=(k<<1)+(k<<3);
    while(k){putchar('0'+x/k%10);k/=10;}
}
inline int read(){
    int ret=0;
    char c=getchar();
    while((c>'9')||(c<'0'))c=getchar();
    while((c>='0')&&(c<='9'))ret=(ret<<1)+(ret<<3)+c-'0',c=getchar();
    return ret;
}
void add(int k){
    a1[k]++;
    if(a1[k]==1)block[belong[k]]++;
}
void dec(int k){
    a1[k]--;
    if(a1[k]==0)block[belong[k]]--;
}
inline void query(int l,int r,int k){
    if(belong[r]==belong[l]){
        for(int i=l;i<=r;i++)ans[k]+=(a1[i]>0);
        return;
    }
    for(int i=belong[l]+1;i<belong[r];i++)ans[k]+=block[i];
    if(l%size>(size>>1))for(int i=l;i<(belong[l]+1)*size;i++)ans[k]+=(a1[i]>0);
    else{
        ans[k]+=block[belong[l]];
        for(int i=belong[l]*size;i<l;i++)ans[k]-=(a1[i]>0);
    }
    if(r%size<(size>>1))for(int i=belong[r]*size;i<=r;i++)ans[k]+=(a1[i]>0);
    else{
        ans[k]+=block[belong[r]];
        for(int i=r+1;i<(belong[r]+1)*size;i++)ans[k]-=(a1[i]>0);
    }
}
int main(){
    n=read();m=read();
    size=int(sqrt(n)+0.00001);
    for(int i=0;i<n;i++)a[i]=read()-1;
    for(int i=0;i<n;i++)belong[i]=i/size;
    for(int i=1;i<=m;i++)q[i].l=read()-1,q[i].r=read()-1,q[i].L=read()-1,q[i].R=read()-1,q[i].k=i;
    sort(q+1,q+1+m,cmp);
    for(int i=q[1].l;i<=q[1].r;i++)add(a[i]);
    query(q[1].L,q[1].R,q[1].k);
    l=q[1].l;r=q[1].r;
    for(int i=2;i<=m;i++){
        if(q[i].l>r){
            for(int j=l;j<=r;j++)dec(a[j]);
            for(int j=q[i].l;j<=q[i].r;j++)add(a[j]);
            l=q[i].l;r=q[i].r;
        }
        while(l>q[i].l)add(a[--l]);
        while(r<q[i].r)add(a[++r]);
        while(l<q[i].l)dec(a[l++]);
        while(r>q[i].r)dec(a[r--]);
        query(q[i].L,q[i].R,q[i].k);
    }
    for(int i=1;i<=m;i++){write(ans[i]);puts("");}
}

wyx说他是直接交了3236的，然后就过了，我看了一下发现他size是sqrt(n)/2，然后

Orzwyx

2120

昨天看发现去年4月我写暴力A掉了

因为修改只有1000，所以我们可以选择很好写的带修改莫队，但是作为一个log²的忠实信仰者，我果断写了整体二分，然后跑得和一些暴力差不多快_(:зゝ∠)_Orz qiancl wyx Dirak里面的set手写BST也可以，说不定会变快

#include<cstdio>
#include<set>
using namespace std;
int nex[10005],pre[10005],head[1000005],a[10005],ans[10005],tree[10005];
char S[2];
struct work{
	int x,y,t,v;
}w[16005],wtmp1[16005],wtmp2[16005];
struct query{
	int x,y,t,v,p;
}q[20005],qtmp1[20005],qtmp2[20005];
set<int>s[1000005];
int n,m,wcnt,qcnt,Qcnt;
inline int read(){
    int ret=0;
    char c=getchar();
    while((c>'9')||(c<'0'))c=getchar();
    while((c>='0')&&(c<='9'))ret=(ret<<1)+(ret<<3)+c-'0',c=getchar();
    return ret;
}
inline int lowbit(int k){return k&-k;}
void add(int k,int x){while(k<=n){tree[k]+=x;k+=lowbit(k);}}
inline int sum(int k){int ans=0;while(k){ans+=tree[k];k-=lowbit(k);}return ans;}
void cdq(int l,int r,int wl,int wr,int ql,int qr){
	if(l==r)return;
	int wcnt1=0,wcnt2=0,qcnt1=0,qcnt2=0,k=wl,mid=(l+r)>>1;
	for(int i=ql;i<=qr;i++){
		while((w[k].t<q[i].t)&&(k<=wr)){
			if(w[k].x<=mid){
				add(w[k].y,w[k].v);
				wtmp1[++wcnt1]=w[k];
			}else wtmp2[++wcnt2]=w[k];
			k++;
		}
		if(k==wl)continue;
		if(q[i].x<=mid)qtmp1[++qcnt1]=q[i];
		else{
			qtmp2[++qcnt2]=q[i];
			ans[q[i].p]+=q[i].v*sum(q[i].y);
		}
	}
	for(int i=1;i<=wcnt1;i++){add(wtmp1[i].y,-wtmp1[i].v);w[wl+i-1]=wtmp1[i];}
	for(int i=1;i<=wcnt2;i++)w[wl+wcnt1+i-1]=wtmp2[i];
	for(int i=1;i<=qcnt1;i++)q[ql+i-1]=qtmp1[i];
	for(int i=1;i<=qcnt2;i++)q[ql+qcnt1+i-1]=qtmp2[i];
	if((wcnt1)&&(qcnt1))cdq(l,mid,wl,wl+wcnt1-1,ql,ql+qcnt1-1);
	if((wcnt2)&&(qcnt2))cdq(mid+1,r,wl+wcnt1,wl+wcnt1+wcnt2-1,ql+qcnt1,ql+qcnt1+qcnt2-1);
}
int main(){
	n=read();m=read();
	for(int i=1;i<=n;i++){
		a[i]=read();
		if(head[a[i]])nex[head[a[i]]]=i;
		pre[i]=head[a[i]];head[a[i]]=i;
		w[++wcnt]=(work){i,pre[i]+1,0,1};s[a[i]].insert(i);
	}
	for(int i=1;i<=m;i++){
		scanf("%s",S);int l=read(),r=read();
		if(S[0]=='Q'){
			q[++qcnt]=(query){r+1,l,i,1,++Qcnt};
			if(l>1)q[++qcnt]=(query){l,l,i,-1,Qcnt};
		}else{
			if(a[l]==r)continue;
			w[++wcnt]=(work){l,pre[l]+1,i,-1};
			s[a[l]].erase(l);
			set<int>::iterator ine=s[r].upper_bound(l);
			if(nex[l]){
				w[++wcnt]=(work){nex[l],l+1,i,-1};
				w[++wcnt]=(work){nex[l],pre[l]+1,i,1};
			}
			if(nex[l])pre[nex[l]]=pre[l];
			if(pre[l])nex[pre[l]]=nex[l];
			int p;
			if(ine!=s[r].end()){
				p=*ine;nex[l]=p;
				w[++wcnt]=(work){p,pre[p]+1,i,-1};
				w[++wcnt]=(work){p,l+1,i,1};
				pre[p]=l;
			}else nex[l]=0;
			if(ine!=s[r].begin()){
				ine--,p=*ine;
				nex[p]=l;
			}else p=0;
			pre[l]=p;a[l]=r;s[r].insert(l);
			w[++wcnt]=(work){l,p+1,i,1};
		}
	}
	cdq(1,n+1,1,wcnt,1,qcnt);
	for(int i=1;i<=Qcnt;i++)printf("%d\n",ans[i]);
}

2453

2120的双倍经验题

啊那么这个坑就算填完了，我去做一点树套树提神醒脑