莫队的坑等有时间再填
普通莫队：
#include<iostream>
#include<cstdio>
#include<algorithm>
#include<cstring>
#include<vector>
#include<cmath>
#include<queue>
#include<map>
#define inf 2000000000
#define rep(i,a,b) for(int i=(a);i<=(b);++i)
#define dwn(i,a,b) for(int i=(a);i>=(b);--i)
using namespace std;
typedef long long ll;
int n,m,len,l=1,r=0,c[50010],b[50010];
ll ans=0,sum[50010];
struct MO
{
int l,r,id;ll A,B;
}a[50010];
int read()
{
int x=0,f=1;
char ch=getchar();
while(ch<'0'||ch>'9')
{
if(ch=='-') f=-1;
ch=getchar();
}
while(ch>='0'&&ch<='9')
{
x=(x<<3)+(x<<1)+(ch^48);
ch=getchar();
}
return x*f;
}
ll gcd(ll a,ll b){while(b^=a^=b^=a%=b);return a;}
bool cmp1(MO x,MO y){return b[x.l]==b[y.l]?x.r<y.r:x.l<y.l;}
bool cmp2(MO x,MO y){return x.id<y.id;}
void add(int x,int d)
{
ans-=sum[x]*sum[x];
sum[x]+=d;
ans+=sum[x]*sum[x];
}
int main()
{
n=read(),m=read();
rep(i,1,n) c[i]=read();
rep(i,1,m) a[i].l=read(),a[i].r=read(),a[i].id=i;
len=sqrt(n);
rep(i,1,n) b[i]=(i-1)/len+1;
sort(a+1,a+m+1,cmp1);
rep(i,1,m)
{
while(l<a[i].l){add(c[l],-1);++l;}
while(l>a[i].l){--l;add(c[l],1);}
while(r<a[i].r){++r;add(c[r],1);}
while(r>a[i].r){add(c[r],-1);--r;}
if(a[i].l==a[i].r){a[i].A=0;a[i].B=1;continue;}
a[i].A=ans-(a[i].r-a[i].l+1);
a[i].B=1ll*(a[i].r-a[i].l+1)*(a[i].r-a[i].l);
ll d=gcd(a[i].A,a[i].B);
a[i].A/=d,a[i].B/=d;
}
sort(a+1,a+m+1,cmp2);
rep(i,1,m)
printf("%lld/%lld
",a[i].A,a[i].B);
return 0;
}
带修莫队：
本题由于管理员在8.11加强数据 莫队要吸氧过(吸氧后跑的飞起来)
#include<iostream>
#include<cstdio>
#include<algorithm>
#include<cstring>
#include<vector>
#include<cmath>
#include<queue>
#include<map>
#define inf 2000000000
#define rep(i,a,b) for(int i=(a);i<=(b);++i)
#define dwn(i,a,b) for(int i=(a);i>=(b);--i)
using namespace std;
typedef long long ll;
int n,m,len,times,T=0,l=1,r=0,ANS=0,tot=0,b[140010],now[140010],col[1000010],ans[140010],sum[140010];
struct Q
{
int l,r,tim,id;
}q[140010];
struct R
{
int x,nw,old;
}c[140010];
int read()
{
int x=0,f=1;
char ch=getchar();
while(ch<'0'||ch>'9')
{
if(ch=='-') f=-1;
ch=getchar();
}
while(ch>='0'&&ch<='9')
{
x=(x<<3)+(x<<1)+(ch^48);
ch=getchar();
}
return x*f;
}
bool cmp(Q x,Q y){return b[x.l]==b[y.l]?(b[x.r]==b[y.r]?x.tim<y.tim:x.r<y.r):x.l<y.l;}
inline void add(int x,int d)
{
col[x]+=d;
if(d>0) ANS+=(col[x]==1);
if(d<0) ANS-=(col[x]==0);
}
inline void altim(int x,int d)
{
if(l<=x&&x<=r) add(sum[x],-1),add(d,1);
sum[x]=d;
}
int main()
{
n=read(),m=read();
len=pow(n,2.0/3);
rep(i,1,n) sum[i]=now[i]=read();
rep(i,1,n) b[i]=(i-1)/len+1;
rep(i,1,m)
{
char type=getchar();
while(type==' '||type=='
') type=getchar();
int x=read(),y=read();
if(type=='Q') tot++,q[tot]=(Q){x,y,times,tot};
if(type=='R') times++,c[times]=(R){x,y,now[x]},now[x]=y;
}
sort(q+1,q+tot+1,cmp);
rep(i,1,tot)
{
while(T<q[i].tim){T++;altim(c[T].x,c[T].nw);}
while(T>q[i].tim){altim(c[T].x,c[T].old);T--;}
while(l<q[i].l){add(sum[l],-1);l++;}
while(l>q[i].l){l--;add(sum[l],1);}
while(r<q[i].r){r++;add(sum[r],1);}
while(r>q[i].r){add(sum[r],-1);r--;}
ans[q[i].id]=ANS;
}
rep(i,1,tot)
printf("%d
",ans[i]);
return 0;
}
树上带修莫队：
//https://www.lydsy.com/JudgeOnline/problem.php?id=4129
//Haruna's Breakfast
#include<iostream>
#include<cstdio>
#include<algorithm>
#include<cstring>
#include<vector>
#include<cmath>
#include<queue>
#include<map>
#include<stack>
#define inf 2000000000
#define rep(i,a,b) for(int i=(a);i<=(b);++i)
#define dwn(i,a,b) for(int i=(a);i>=(b);--i)
using namespace std;
typedef long long ll;
const int N=50000;
stack<int> st;
int n,m,len,x,y,lum=0,T=0,cnt=0,times=0,root=1,ans[N+10],sum[N+10],now[N+10],a[N+10],b[N+10],dep[N+10],lg[N+10],f[N+10][20];
int tot=0,head[N+10];
ll tree[N+10];
bool v[N+10];
struct EDGE
{
int to,nxt;
}edge[2*N+10];
struct Q
{
int x,y,tim,id;
}q[N+10];
struct C
{
int x,nw,old;
}c[N+10];
void add(int u,int v)
{
edge[++tot].to=v;
edge[tot].nxt=head[u];
head[u]=tot;
}
void dfs(int x,int fa)
{
dep[x]=dep[fa]+1;
f[x][0]=fa;
rep(i,1,lg[dep[x]])
f[x][i]=f[f[x][i-1]][i-1];
for(int i=head[x];i;i=edge[i].nxt)
{
int y=edge[i].to;
if(y==fa) continue;
dfs(y,x);
if(st.size()>=len)
{
++lum;
while(!st.empty()) b[st.top()]=lum,st.pop();
}
}
st.push(x);
}
int lca(int x,int y)
{
if(dep[x]>dep[y]) swap(x,y);
dwn(i,lg[dep[y]-dep[x]],0)
if(dep[f[y][i]]>=dep[x]) y=f[y][i];
if(x==y) return x;
dwn(i,lg[dep[x]],0)
if(f[x][i]!=f[y][i]) x=f[x][i],y=f[y][i];
return f[x][0];
}
int read()
{
int x=0,f=1;
char ch=getchar();
while(ch<'0'||ch>'9')
{
if(ch=='-') f=-1;
ch=getchar();
}
while(ch>='0'&&ch<='9')
{
x=(x<<3)+(x<<1)+(ch^48);
ch=getchar();
}
return x*f;
}
inline int lowbit(int x)
{
return x&-x;
}
void ask_add(int x,int d)
{
if(x>n) return;
sum[x]+=d;
if((d<0&&sum[x]==0)||(d>0&&sum[x]==1))
for(;x<=n;x+=lowbit(x))
tree[x]+=d;
}
int ask_sum(int x)
{
int ans=0;
for(;x>0;x-=lowbit(x))
ans+=tree[x];
return ans;
}
bool cmp(Q x,Q y)
{
return b[x.x]==b[y.x]?(b[x.y]==b[y.y]?x.tim<y.tim:x.y<y.y):x.x<y.x;
}
void revise(int x,int d)
{
if(v[x])
{
ask_add(a[x],-1);
ask_add(d,1);
}
a[x]=d;
}
void run(int x)
{
if(v[x])
{
v[x]=0;
ask_add(a[x],-1);
}
else
{
v[x]=1;
ask_add(a[x],1);
}
}
void mov(int x,int y)
{
if(dep[x]>dep[y]) swap(x,y);
while(dep[x]<dep[y]) run(y),y=f[y][0];
while(x!=y) run(x),run(y),x=f[x][0],y=f[y][0];
}
int ask_ans()
{
int ans,l=1,r=n;
while(l<=r)
{
int mid=(l+r)>>1;
if(ask_sum(mid)==mid) ans=mid+1,l=mid+1;
else ans=mid,r=mid-1;
}
return ans;
}
int main()
{
n=read(),m=read();len=pow(n,0.45);
rep(i,1,n) a[i]=now[i]=read()+1;
rep(i,1,n-1)
{
int u=read(),v=read();
add(u,v),add(v,u);
}
rep(i,2,n) lg[i]=lg[i>>1]+1;
dfs(root,0);++lum;while(!st.empty()) b[st.top()]=lum,st.pop();
rep(i,1,m)
{
int op=read(),x=read(),y=read();
if(op==0) ++times,c[times].x=x,c[times].nw=y+1,c[times].old=now[x],now[x]=y+1;
if(op==1) ++cnt,q[cnt].x=x,q[cnt].y=y,q[cnt].tim=times,q[cnt].id=cnt;
}
x=y=root;
sort(q+1,q+cnt+1,cmp);
rep(i,1,cnt)
{
while(T<q[i].tim) T++,revise(c[T].x,c[T].nw);
while(T>q[i].tim) revise(c[T].x,c[T].old),T--;
if(x!=q[i].x) mov(x,q[i].x),x=q[i].x;
if(y!=q[i].y) mov(y,q[i].y),y=q[i].y;
int anc=lca(x,y);
run(anc);
ans[q[i].id]=ask_ans()-1;
run(anc);
}
rep(i,1,cnt)
printf("%d
",ans[i]);
return 0;
}