杜教筛
#include<bits/stdc++.h>
#include<tr1/unordered_map>
#define LL long long
#define Maxn 3000000
using namespace std;
LL T,N;
LL cnt=0,prime[Maxn+5],mu[Maxn+5],phi[Maxn+5];
bool is_prime[Maxn+5];
LL Sum_Mu[Maxn+5],Sum_Phi[Maxn+5];
tr1::unordered_map<LL,LL> SUM_MU,SUM_PHI;
inline void Read(LL &x)
{
LL f=1;x=0;char ch=getchar();
while (!isdigit(ch)){if (ch=='-') f=-1;ch=getchar();}
while (isdigit(ch)){x=x*10+ch-'0';ch=getchar();}
x*=f;
}
LL Get_Mu_Sum(LL X)
{
if (X<=Maxn) return Sum_Mu[X];
if (SUM_MU[X]) return SUM_MU[X];
LL res=1;
for (LL l=2,r;l<=X;l=r+1)
{
r=X/(X/l);
res-=(r-l+1)*Get_Mu_Sum(X/l);
}
return SUM_MU[X]=res;
}
LL Get_Phi_Sum(LL X)
{
if (X<=Maxn) return Sum_Phi[X];
if (SUM_PHI[X]) return SUM_PHI[X];
LL res=(X+1)*X/2;
for (LL l=2,r;l<=X;l=r+1)
{
r=X/(X/l);
res-=(r-l+1)*Get_Phi_Sum(X/l);
}
return SUM_PHI[X]=res;
}
void Get(LL X)
{
memset(is_prime,1,sizeof(is_prime));
is_prime[0]=is_prime[1]=0;mu[1]=1;phi[1]=1;
for (LL i=1;i<=Maxn;i++)
{
if (is_prime[i]) prime[++cnt]=i,mu[i]=-1,phi[i]=i-1;
for (LL j=1;j<=cnt&&i*prime[j]<=Maxn;j++)
{
is_prime[i*prime[j]]=0;
mu[i*prime[j]]=-mu[i];
phi[i*prime[j]]=phi[i]*phi[prime[j]];
if (i%prime[j]==0){mu[i*prime[j]]=0;phi[i*prime[j]]=phi[i]*prime[j];break;}
}
}
for (LL i=1;i<=Maxn;i++) Sum_Mu[i]=Sum_Mu[i-1]+mu[i],Sum_Phi[i]=Sum_Phi[i-1]+phi[i];
}
int main()
{
Read(T);
Get(N);
while (T--)
{
Read(N);
cout<<Get_Phi_Sum(N)<<" "<<Get_Mu_Sum(N)<<endl;
}
return 0;
}
点分治
#include<bits/stdc++.h>
using namespace std;
struct node{int next,to,dis;}e[40005*2];
int K,N,cnt=0,head[40005],size[40005],Minn=2e9,rt,len[40005],D[40005],Ans=0,l,r;
bool vis[40005];
inline void Read(int &x)
{
int f=1;x=0;char ch=getchar();
while (!isdigit(ch)){if (ch=='-') f=-1;ch=getchar();}
while (isdigit(ch)){x=x*10+ch-'0';ch=getchar();}
x*=f;
}
inline void add(int a,int b,int c)
{
e[++cnt].next=head[a],e[cnt].to=b,e[cnt].dis=c,head[a]=cnt;
}
inline void Get_dis(int now,int fa)
{
D[++r]=len[now];
for (int i=head[now];i;i=e[i].next)
{
int v=e[i].to;
if (vis[v]||v==fa) continue;
len[v]=len[now]+e[i].dis;
Get_dis(v,now);
}
}
inline void Get_rt(int now,int fa,int Size)
{
size[now]=1;int Max_size=0;
for (int i=head[now];i;i=e[i].next)
{
int v=e[i].to;
if (vis[v]||v==fa) continue;
Get_rt(v,now,Size);
size[now]+=size[v];
Max_size=max(size[v],Max_size);
}
Max_size=max(Max_size,Size-size[now]);
if (Minn>Max_size) rt=now,Minn=Max_size;
}
inline int solve(int rt,int val)
{
l=1,r=0;
int ans=0;
len[rt]=val;
Get_dis(rt,rt);
sort(D+1,D+r+1);
while (l<r)
{
if (D[l]+D[r]<=K) ans+=r-l,l++;
else r--;
}
return ans;
}
inline void Get_Ans(int now)
{
vis[now]=1;
Ans+=solve(rt,0);
for (int i=head[now];i;i=e[i].next)
{
int v=e[i].to;
if (vis[v]) continue;
Ans-=solve(v,e[i].dis);
Minn=2e9;
Get_rt(v,v,size[v]);
Get_Ans(rt);
}
}
int main()
{
memset(vis,0,sizeof(vis));
Read(N);
for (int i=1;i<=N-1;i++)
{
int a,b,c;
Read(a),
Read(b),
Read(c);
add(a,b,c),
add(b,a,c);
}
Read(K);
Get_rt(1,1,N);
Get_Ans(rt);
cout<<Ans<<endl;
return 0;
}
BSGS&exBSGS
#include<bits/stdc++.h>
using namespace std;
long long b,p,a;
void Read(long long &x)
{
long long f=1;x=0;char ch=getchar();
while (!isdigit(ch)){if (ch=='-') f=-1;ch=getchar();}
while (isdigit(ch)){x=x*10+ch-'0';ch=getchar();}
x*=f;
}
long long gcd(long long a,long long b)
{
if (b==0) return a;
return gcd(b,a%b);
}
long long KSM(long long base,long long index,long long p)
{
long long Res=1;
while (index)
{
if (index%2==1) Res*=base,Res%=p;
base*=base;
base%=p;
index/=2;
}
return Res%p;
}
void ex_gcd(long long a,long long b,long long &d,long long &x,long long &y) {
if (b==0) x=1,y=0,d=a;
else
{
ex_gcd(b,a%b,d,x,y);
long long tmp=x;x=y;y=tmp-a/b*y;
}
}
long long inv(long long a,long long b)
{
long long x,y,d;
ex_gcd(a,b,d,x,y);
return (x%b+b)%b;
}
long long BSGS(long long a,long long b,long long p)
{
map <long long,long long> m;
long long X=(long long)ceil(sqrt(p));
m[b]=0;
long long Ans_=b;
for (int i=1;i<=X;i++) Ans_*=a,Ans_%=p,m[Ans_]=i;
long long Ans__=KSM(a,X,p);
long long Ans___=1,Ans=-1;
for (int i=1;i<=X;i++)
{
Ans___*=Ans__,Ans___%=p;
if (m.count(Ans___)) {Ans=i*X-m[Ans___];break;}
}
return Ans;
}
long long exBSGS(long long a,long long b,long long p)
{
if (b==1||p==1)return 0;
long long g=gcd(a,p),k=0,na=1;
while (g!=1)
{
if (b%g!=0)return -1;
k++;b/=g;p/=g;na=na*(a/g)%p;
if (na==b)return k;
g=gcd(a,p);
}
long long f=BSGS(a%p,b*inv(na,p)%p,p);
if (f==-1)return -1;
return f+k;
}
int main()
{
while (1)
{
Read(a),Read(p),Read(b);
if (p==0||a==0||b==0) break;
long long answer=exBSGS(a,b,p);
if (answer==-1) cout<<"No Solution"<<endl;
else cout<<answer<<endl;
}
return 0;
}
FastIO读写优化
struct FastIO{
static const int S=1048576;
char buf[S],*L,*R;int stk[20],Top;
~FastIO(){clear();}
inline char nc(){return L==R&&(R=(L=buf)+fread(buf,1,S,stdin),L==R)?EOF:*L++;}
inline void clear(){fwrite(buf,1,Top,stdout);Top=0;}
inline void pc(char ch){Top==S&&(clear(),0);buf[Top++]=ch;}
inline void endl(){pc('\n');}
FastIO& operator >> (int& ret){ret=0;int f=1;char ch=nc();while(ch<'0'||ch>'9'){if(ch=='-')f=-f;ch=nc();}while(ch>='0'&&ch<='9'){ret=ret*10+ch-'0';ch=nc();}ret*=f;return *this;}
FastIO& operator >> (char* s){register int Len=0;register char ch=nc();while(ch!='\n'){*(s+Len)=ch;Len++;ch=nc();}}
FastIO& operator << (int x){if(x<0){pc('-');x=-x;}do{stk[++stk[0]]=x%10;x/=10;}while(x);while(stk[0]) pc('0'+stk[stk[0]--]);return *this;}
FastIO& operator << (char ch){pc(ch);return *this;}
FastIO& operator << (string str){register int Len=str.size()-1;for(stk[0]=0;Len>=0;Len--) stk[++stk[0]]=str[Len];while(stk[0]) pc(stk[stk[0]--]);return *this;}
}fin,fout;
KMP
#include<bits/stdc++.h>
using namespace std;
int len1,len2;
char s1[1000010],s2[1000010];
int next[1000010],ans=0;
int main(){
scanf("%s%s",s1,s2);
len1=strlen(s1);len2=strlen(s2);
next[0]=0;
for(int i=1;i<len2;i++){
int temp=next[i-1];
while(temp>0&&s2[temp]!=s2[i]) temp=next[temp-1];
if(s2[i]==s2[temp]) next[i]=temp+1;
next[i]=temp;
}
int j=0;
for(int i=0;i<len1;i++){
while(j!=0&&s1[i]!=s2[j]) j=next[j-1];
if(s1[i]==s2[j]) j++;
if(j==len2){
j=next[j-1];
cout<<i-len2+1<<endl;
}
}
return 0;
}
Tarjan
#include<bits/stdc++.h>
#define MAXM 1000005
#define MAXN 1000005
using namespace std;
int n,m;
int head[MAXN],cnt=0;
int dfn[MAXN],low[MAXN],co[MAXN],col=0,top=0,num=0,st[MAXN];
struct Edge{int next,to;}t[MAXM];
void Tarjan(int u)
{
dfn[u]=low[u]=++num;
st[++top]=u;
for (int i=head[u];i;i=t[i].next)
{
int v=t[i].to;
if (!dfn[v])
{
Tarjan(v);
low[u]=min(low[u],low[v]);
}else
if (!co[v]) low[u]=min(low[u],dfn[v]);
}
if (low[u]==dfn[u])
{
co[u]=++col;
while (st[top]!=u)
{
co[st[top]]=col;
--top;
}
--top;
}
}
void add(int a,int b)
{
t[++cnt].next=head[a];
t[cnt].to=b;
head[a]=cnt;
}
int main()
{
scanf("%d%d",&n,&m);
for (int i=1;i<=m;i++)
{
int a,b;
scanf("%d%d",&a,&b);
add(a,b);
}
for (int i=1;i<=n;i++) if (!dfn[i]) Tarjan(i);
for (int i=1;i<=n;i++) cout<<co[i]<<endl;
return 0;
}
/*
6 8
1 3
3 5
5 6
4 6
2 4
1 2
4 1
3 4
*/
SPFA
#include<bits/stdc++.h>
const long long inf=2147483647;
const int maxn=10005;
const int maxm=500005;
using namespace std;
int n,m,s,num_edge=0;
int dis[maxn],vis[maxn],head[maxm];
struct Edge
{
int next,to,dis;
}edge[maxm]; //结构体表示静态邻接表
void addedge(int from,int to,int dis) //邻接表建图
{ //以下是数据结构书上的标准代码，不懂翻书看解释
edge[++num_edge].next=head[from]; //链式存储下一条出边
edge[num_edge].to=to; //当前节点编号
edge[num_edge].dis=dis; //本条边的距离
head[from]=num_edge; //记录下一次的出边情况
}
void spfa()
{
queue<int> q; //spfa用队列，这里用了STL的标准队列
for(int i=1; i<=n; i++)
{
dis[i]=inf; //带权图初始化
vis[i]=0; //记录点i是否在队列中，同dijkstra算法中的visited数组
}
q.push(s); dis[s]=0; vis[s]=1; //第一个顶点入队，进行标记
while(!q.empty())
{
int u=q.front(); //取出队首
q.pop(); vis[u]=0; //出队标记
for(int i=head[u]; i; i=edge[i].next) //邻接表遍历，不多解释了（也可用vector代替）
{
int v=edge[i].to;
if(dis[v]>dis[u]+edge[i].dis) //如果有最短路就更改
{
dis[v]=dis[u]+edge[i].dis;
if(vis[v]==0) //未入队则入队
{
vis[v]=1; //标记入队
q.push(v);
}
}
}
}
}
int main()
{
cin>>n>>m>>s;
for(int i=1; i<=m; i++)
{
int f,g,w;
cin>>f>>g>>w;
addedge(f,g,w); //建图，有向图连一次边就可以了
}
spfa(); //开始跑spfa
for(int i=1; i<=n; i++)
if(s==i) cout<<0<<" "; //如果是回到自己，直接输出0
else cout<<dis[i]<<" "; //否则打印最短距离
return 0;
} //结束
倍增LCA
#include<bits/stdc++.h>
using namespace std;
int tot=0,n,m,s;
int to[1000005],next[1000005],head[1000005];
int deep[1000005],f[1000005][25];
void read(int &x)
{
int f=1;x=0;
char s=getchar();
while(s<'0'||s>'9'){if(s=='-')f=-1;s=getchar();}
while(s>='0'&&s<='9'){x=x*10+s-'0';s=getchar();} x*=f;
}
inline void add(int a,int b)
{
next[++tot]=head[a];head[a]=tot;to[tot]=b;
}
inline void dfs(int u,int fa)
{
deep[u]=deep[fa]+1;
f[u][0]=fa;
for (int i=1;(1<<i)<=deep[u];i++) f[u][i]=f[f[u][i-1]][i-1];
for (int e=head[u];e;e=next[e])
{
int v=to[e];
if (v==fa) continue;
dfs(v,u);
}
}
inline int LCA(int x,int y)
{
if (deep[x]<deep[y]) swap(x,y);
for (int i=20;i>=0;i--)
{
if (deep[f[x][i]]>=deep[y]) x=f[x][i];
if (x==y) return x;
}
for(int i=20;i>=0;i--)
{
if(f[x][i]!=f[y][i]) x=f[x][i],y=f[y][i];
}
return f[x][0];
}
int main()
{
read(n);read(m);read(s);
for (int i=1;i<=n-1;i++)
{
int a,b;
read(a);read(b);
add(a,b);
add(b,a);
}
dfs(s,0);
for (int i=1;i<=m;i++)
{
int a,b;
read(a);read(b);
cout<<LCA(a,b)<<endl;
}
return 0;
}
Kruskal
// luogu-judger-enable-o2
#include<bits/stdc++.h>
using namespace std;
struct node{int u,v,w;}x[200005];
int fa[5005],ans=0,N,M;
bool flag=0;
bool cmp(node a,node b){return a.w<b.w;}
inline int getfa(int x)
{
if (x==fa[x]) return x;
return fa[x]=getfa(fa[x]);
}
void Kruskal()
{
int cnt=0;
for (int i=1;i<=M;i++)
{
int fx=getfa(x[i].u);
int fy=getfa(x[i].v);
if (fx!=fy)
{
cnt++;
fa[fy]=fx;
ans+=x[i].w;
if (cnt==N-1){flag=1;cout<<ans<<endl;break;};
}
}
if (flag==0) cout<<"-1"<<endl;
}
int main()
{
scanf("%d%d",&N,&M);
for (int i=1;i<=N;i++) fa[i]=i;
for (int i=1;i<=M;i++) scanf("%d%d%d",&x[i].u,&x[i].v,&x[i].w);
sort(x+1,x+M+1,cmp);
Kruskal();
return 0;
}
分块
#include<bits/stdc++.h>
using namespace std;
struct block{int l;int r;int tag;}k[1000005];
int num[1000005],a[1000005],N;
void build()
{
int len=sqrt(N);
int tot=N/len;
if (N%len) tot++;
for (int i=1;i<=tot;i++)
{
k[i].l=(i-1)*len+1;
k[i].r=i*len;
}
k[tot].r=N;
for (int i=1;i<=N;i++) num[i]=(i-1)/len+1;
}
void add(int x,int y,int z)
{
if (num[x]==num[y])
{
for (int i=x;i<=y;i++) a[i]+=z;
}
else
{
for (int i=x;i<=k[num[x]].r;i++) a[i]+=z;
for (int i=num[x]+1;i<num[y];i++) k[i].tag+=z;
for (int i=k[num[y]].l;i<=y;i++) a[i]+=z;
}
}
int ask(int x)
{
return a[x]+k[num[x]].tag;
}
int main()
{
scanf("%d",&N);
for (int i=1;i<=N;i++) scanf("%d",&a[i]);
build();
for (int i=1;i<=N;i++)
{
int opt,l,r,c;
scanf("%d%d%d%d",&opt,&l,&r,&c);
if (opt==0) add(l,r,c);
else cout<<ask(r)<<endl;
}
return 0;
}
换根树剖
#include<bits/stdc++.h>
#define MAXN 500005
#define MAXM 500005
long long n,m,SUMM,r=1,p;
long long seg[MAXN],rev[MAXM],size[MAXN],son[MAXN],top[MAXN],dep[MAXN];
long long sum[4*MAXM],num[MAXN],fa[MAXN],Add[4*MAXN];
long long first[2*MAXM],nex[2*MAXM],go[2*MAXM];
using namespace std;
inline long long query(long long root,long long l,long long r,long long L,long long R)
{
if (L>r||R<l) return 0;
if (L<=l&&r<=R) return sum[root]+(r-l+1)*Add[root];
long long res=(min(R,r)-max(l,L)+1)*Add[root];
long long mid=(l+r)/2;
if (mid>=L) res+=query(root<<1,l,mid,L,R);
if (mid+1<=R) res+=query(root<<1|1,mid+1,r,L,R);
return res;
}
inline void change(long long root,long long l,long long r,long long Val,long long pos)
{
if (pos>r||pos<l) return;
if (l==r&&r==pos)
{
sum[root]=Val;
return;
}
long long mid=(l+r)/2;
if (mid>=pos) change(root*2,l,mid,Val,pos);
if (mid+1<=pos) change(root*2+1,mid+1,r,Val,pos);
sum[root]=sum[root<<1]+sum[root<<1|1];
}
inline void dfs1(long long u,long long f)
{
size[u]=1;
fa[u]=f;
dep[u]=dep[f]+1;
for (long long e=first[u];e;e=nex[e])
{
long long v=go[e];
if (v==f) continue;
dfs1(v,u);
size[u]+=size[v];
if (size[v]>size[son[u]]) son[u]=v;
}
}
inline void dfs2(long long u,long long f)
{
if (son[u])
{
seg[son[u]]=++seg[0];
top[son[u]]=top[u];
rev[seg[0]]=son[u];
dfs2(son[u],u);
}
for (long long e=first[u];e;e=nex[e])
{
long long v=go[e];
if (!top[v])
{
seg[v]=++seg[0];
rev[seg[0]]=v;
top[v]=v;
dfs2(v,u);
}
}
}
inline void modify(long long root,long long maxl,long long maxr,long long l,long long r,long long v)
{
if (maxl>=l&&maxr<=r){Add[root]+=v;return;}
sum[root]+=(min(maxr,r)-max(maxl,l)+1)*v;
long long mid=(maxl+maxr)/2;
if (l<=mid) modify(root*2,maxl,mid,l,r,v);
if (mid<r) modify(root*2+1,mid+1,maxr,l,r,v);
}
inline void build(long long root,long long l,long long r)
{
long long mid=(l+r)/2;
if (l==r)
{
sum[root]=num[rev[l]];
return;
}
build(root<<1,l,mid);
build(root<<1|1,mid+1,r);
sum[root]=sum[root<<1]+sum[root<<1|1];
}
long long tot=0;
inline void add(long long x,long long y)
{
nex[++tot]=first[x];
go[tot]=y;
first[x]=tot;
}
inline void insert(long long x,long long y){add(x,y);add(y,x);}
inline long long read()
{
char chr;
long long f=1;
while (((chr=getchar())<'0')||(chr>'9')){if (chr=='-'){f=-1;}}
long long res=chr-'0';
while (((chr=getchar())>='0')&&(chr<='9')){res=res*10+chr-'0';}
return res*f;
}
long long LCA(long long u,long long v)
{
long long ans=0;
while (top[u]!=top[v]){
if (dep[top[u]]<dep[top[v]]){
swap(u,v);
}
u=fa[top[u]];
}
if (dep[u]>dep[v]){
swap(u,v);
}
return u;
}
long long LCA2(long long u,long long v){return max(LCA(u,v),max(LCA(u,r),LCA(v,r)));}
int get(int u,int v)
{
while (top[u]!=top[v])
{
u=top[u];
if (fa[u]==v) return u;
u=fa[u];
}
return son[v];
}
int main()
{
n=read(); m=read();
for (long long i=1;i<=n;i++) num[i]=read();
for (long long i=1;i<n;i++) insert(read(),read());
dfs1(r,r);
seg[0]=seg[r]=1;rev[1]=r;top[r]=r;
dfs2(r,r);
build(1,1,seg[0]);
for (int i=1;i<=m;i++)
{
long long opt=read(),u,v,x;
if (opt==1) {r=read();continue;}//换根
if (opt==2) //子树加权
{
u=read();v=read();x=read();
long long now=LCA2(u,v);
//cout<<"LCA "<<u<<" "<<v<<"="<<now<<endl;
if (now==r){modify(1,1,seg[0],seg[1],seg[1]+size[1]-1,x);continue;}
if (LCA(now,r)==now) {long long tmp=get(r,now);modify(1,1,seg[0],seg[1],seg[1]+size[1]-1,x);modify(1,1,seg[0],seg[tmp],seg[tmp]+size[tmp]-1,-x);}else modify(1,1,seg[0],seg[now],seg[now]+size[now]-1,x);
}
if (opt==3)//子树求和
{
u=read();
if (r==u) {cout<<query(1,1,seg[0],seg[1],seg[1]+size[1]-1)<<endl;continue;}
if (LCA(u,r)==u){long long tmp=get(r,u);cout<<query(1,1,seg[0],seg[1],seg[1]+size[1]-1)-query(1,1,seg[0],seg[tmp],seg[tmp]+size[tmp]-1)<<endl;}else cout<<query(1,1,seg[0],seg[u],seg[u]+size[u]-1)<<endl;
//if (LCA(u,r)==u) cout<<"Fuckever"<<" "<<query(1,1,seg[0],seg[u]+1,seg[u]+size[u]-1)<<endl;
}
}
return 0;
}
trie
#include<bits/stdc++.h>
#define MAXN 1005
using namespace std;
int ch[MAXN][10005],tot=0,n,m;
bool f[MAXN];
void insert(char s[])
{
int len=strlen(s),p=1;
for(int i=0;i<len;i++)
{
int t=s[i]-'a';
if(ch[p][t]==0)
{
ch[p][t]=++tot;
p=ch[p][t];
}
f[p]=1;
}
}
int find(char s[])
{
int p=1,len=strlen(s);
for(int i=0;i<len;i++)
{
int c=s[i]-'a';
if(ch[p][c]==0) return 0;
p=ch[p][c];
}
return 1;
}
int main()
{
cin>>n>>m;
for (int i=1;i<=n;i++)
{
char s[1005];
cin>>s;
insert(s);
}
for (int i=1;i<=m;i++)
{
char s[1005];
cin>>s;
if (find(s)) cout<<"YES"<<endl;
else cout<<"NO"<<endl;
}
}
CDQ三维偏序
#include<bits/stdc++.h>
#define MAXN 100005
using namespace std;
struct node{int a,b,c,cnt,ans;};
int N,K,Tot=0,F[MAXN];
node Tmp[MAXN],Val[MAXN];
bool Cmp_1(node x,node y){if (x.a!=y.a) return x.a<y.a;else if (x.b!=y.b) return x.b<y.b;else return x.c<y.c;}
bool Cmp_2(node x,node y){if (x.b!=y.b) return x.b<y.b;return x.c<y.c;};
void Read(int &x)
{
int f=1;x=0;char ch=getchar();
while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();}
while(ch>='0'&&ch<='9'){x=x*10+ch-'0';ch=getchar();}
x*=f;
}
struct Seg_Tree
{
int Tree[800010];
void Insert(int root,int l,int r,int num,int cnt)
{
if (l==r) {Tree[root]+=cnt;return;}
int Mid=l+r>>1;
if (num<=Mid) Insert(root<<1,l,Mid,num,cnt);else Insert(root<<1|1,Mid+1,r,num,cnt);
Tree[root]=Tree[root<<1]+Tree[root<<1|1];
}
int ask(int root,int l,int r,int quel,int quer)
{
if (l>quer||r<quel) return 0;
if (quel<=l&&r<=quer) return Tree[root];
int Mid=l+r>>1;
return ask(root<<1,l,Mid,quel,quer)+ask(root<<1|1,Mid+1,r,quel,quer);
}
}seg;
void CDQ(int l,int r)
{
if (l==r) return;
int Mid=l+r>>1;
CDQ(l,Mid); CDQ(Mid+1,r);
sort(Val+l,Val+Mid+1,Cmp_2); sort(Val+Mid+1,Val+r+1,Cmp_2);
int j=l;
for (int i=Mid+1;i<=r;i++)
{
while (j<=Mid&&Val[j].b<=Val[i].b) seg.Insert(1,1,K,Val[j].c,Val[j].cnt),j++;
Val[i].ans+=seg.ask(1,1,K,1,Val[i].c);
}
//cout<<"OK"<<endl;
for (int i=l;i<j;i++) seg.Insert(1,1,K,Val[i].c,-Val[i].cnt);
}
int main()
{
// freopen("testdata.in","r",stdin);
// freopen("testdata.out","w",stdout);
Read(N);Read(K);
for (int i=1;i<=N;i++) Read(Tmp[i].a),Read(Tmp[i].b),Read(Tmp[i].c),Tmp[i].cnt=1;
sort(Tmp+1,Tmp+N+1,Cmp_1);
for (int i=1;i<=N;i++)
{
if (Tmp[i].a==Tmp[i-1].a&&Tmp[i].b==Tmp[i-1].b&&Tmp[i].c==Tmp[i-1].c) Val[Tot].cnt++;
else Val[++Tot]=Tmp[i];
}
//for (int i=1;i<=Tot;i++) printf("%d %d %d %d\n",Val[i].a,Val[i].b,Val[i].c,Val[i].cnt);
CDQ(1,Tot);
for (int i=1;i<=Tot;i++) F[Val[i].ans+Val[i].cnt-1]+=Val[i].cnt;
for (int i=0;i<N;i++) cout<<F[i]<<endl;
//cout<<endl;
//for (int i=1;i<=Tot;i++) cout<<Val[i].ans<<endl;
return 0;
}
对拍
@echo off
:loop
MakeData.exe
a.exe
b.exe
fc a.out b.out
if not errorlevel 1 goto loop
pause
:end
树链剖分
#pragma GCC optimize(2)
#include<bits/stdc++.h>
#define MAXN 101000
#define MAXM 624000
int n,m,SUMM,MAXX;
int seg[MAXN],rev[MAXM],size[MAXN],son[MAXN],top[MAXN],dep[MAXN];
int sum[MAXM],num[MAXN],fa[MAXN],Max[MAXN];
int first[MAXM],next[MAXM],go[MAXM];
using namespace std;
inline void query(int root,int l,int r,int L,int R)
{
if (L>r||R<l) return;
if (L<=l&&r<=R)
{
SUMM+=sum[root];
MAXX=max(MAXX,Max[root]);
return;
}
int mid=(l+r)/2,res=0;
if (mid>=L) query(root<<1,l,mid,L,R);
if (mid+1<=R) query(root<<1|1,mid+1,r,L,R);
}//不多讲,还是线段树
inline void change(int root,int l,int r,int Val,int pos)
{
if (pos>r||pos<l) return;
if (l==r&&r==pos)
{
sum[root]=Val;
Max[root]=Val;
return;
}
int mid=(l+r)/2;
if (mid>=pos) change(root*2,l,mid,Val,pos);
if (mid+1<=pos) change(root*2+1,mid+1,r,Val,pos);
sum[root]=sum[root<<1]+sum[root<<1|1];
Max[root]=max(Max[root<<1],Max[root<<1|1]);
}//不多讲,就是线段树
inline void dfs1(int u,int f)//u为当前点,f为父节点
{
int e;
size[u]=1;//自己是自己子树的一个部分
fa[u]=f;//肯定的
dep[u]=dep[f]+1;//深度比父亲大1
for (int e=first[u];e;e=next[e])//遍历所有与u相连的边
{
int v=go[e];//此边到达的点
if (v==f) continue;//不能是父亲,要不然走上面回去了
dfs1(v,u);//让u当v的父亲再dfs
size[u]+=size[v];//子树u的size=dep[u]-1的所有直连子节点的子树size之和
if (size[v]>size[son[u]]) son[u]=v;//选出一个size最大的直连子节点做重儿子
}
}
inline void dfs2(int u,int f)
{
int e;
if (son[u])//先走重儿子,使重路径在线段树中位置连续
{ //根在这无法赋值,要在主程序中赋值
seg[son[u]]=++seg[0];//seg[0]用于计数,将重儿子放到线段中
top[son[u]]=top[u];//父亲的重链顶端也是重儿子的重链顶端
rev[seg[0]]=son[u];//使线段树第x个位置对应树中的节点编号,rev[seg[x]]=x;
dfs2(son[u],u);//往重儿子处dfs
}
for (e=first[u];e;e=next[e])
{
int v=go[e];
if (!top[v])//没有被遍历过,也就是不是u的重儿子或父亲
{
seg[v]=++seg[0];//同理,将v下放到线段中
rev[seg[0]]=v;//使线段树第x个位置对应树中的节点编号,rev[seg[x]]=x;
top[v]=v;//u,v为轻链,v定为重链开头,也就是top
dfs2(v,u);
}
}
}
inline void build(int root,int l,int r)
{
int mid=(l+r)/2;
if (l==r)
{
Max[root]=sum[root]=num[rev[l]];
return;
}
build(root<<1,l,mid);
build(root<<1|1,mid+1,r);
sum[root]=sum[root<<1]+sum[root<<1|1];
Max[root]=max(Max[root<<1],Max[root<<1|1]);
}//对着线段建树
int tot=0;
inline void add(int x,int y)
{
next[++tot]=first[x];
go[tot]=y;
first[x]=tot;
}
inline void insert(int x,int y){add(x,y);add(y,x);}
inline void ask(int x,int y)
{
int fx=top[x],fy=top[y];
while(fx!=fy)
{
if (dep[fx]<dep[fy]) swap(x,y),swap(fx,fy);
query(1,1,seg[0],seg[fx],seg[x]);//这时的seg[0]也就成为了线段总长
x=fa[fx]; fx=top[x];
}
if (dep[x]>dep[y]) swap(x,y);
query(1,1,seg[0],seg[x],seg[y]);//此时seg[x]为lca(x,y)
}//LCA式路径询问
inline int read()
{
char chr;
int f=1;
while (((chr=getchar())<'0')||(chr>'9')){if (chr=='-'){f=-1;}}
int res=chr-'0';
while (((chr=getchar())>='0')&&(chr<='9')){res=res*10+chr-'0';}
return res*f;
}
int main()
{
//freopen("count1.in","r",stdin);
//freopen("count1.out","w",stdout);
n=read();
for (int i=1;i<n;i++) insert(read(),read());//读入边
for (int i=1;i<=n;i++) num[i]=read();//点的权值
dfs1(1,0);//第一遍dfs，可找出fa,dep,size,son
seg[0]=seg[1]=top[1]=rev[1]=1;
dfs2(1,0);
build(1,1,seg[0]);
m=read();
for (int i=1;i<=m;i++)
{
int u,v;
string s;
cin>>s;
u=read();v=read();
if (s=="CHANGE") change(1,1,seg[0],v,seg[u]);
else
{
SUMM=0;
MAXX=-214748364;
ask(u,v);
if (s=="QMAX") cout<<MAXX<<endl;
if (s=="QSUM") cout<<SUMM<<endl;
}
}
return 0;
}
区间+子树修改查询树链剖分
#include<bits/stdc++.h>
#define MAXN 501000
#define MAXM 1224000
long long n,m,SUMM,r,p;
long long seg[MAXN],rev[MAXM],size[MAXN],son[MAXN],top[MAXN],dep[MAXN];
long long sum[MAXM],num[MAXN],fa[MAXN],Add[MAXN];
long long first[MAXM],next[MAXM],go[MAXM];
using namespace std;
inline long long query(long long root,long long l,long long r,long long L,long long R)
{
if (L>r||R<l) return 0;
if (L<=l&&r<=R) return sum[root]+(r-l+1)*Add[root];
long long res=(min(R,r)-max(l,L)+1)*Add[root];
long long mid=(l+r)/2;
if (mid>=L) res+=query(root<<1,l,mid,L,R);
if (mid+1<=R) res+=query(root<<1|1,mid+1,r,L,R);
return res;
}//不多讲,还是线段树
inline void change(long long root,long long l,long long r,long long Val,long long pos)
{
if (pos>r||pos<l) return;
if (l==r&&r==pos)
{
sum[root]=Val;
return;
}
long long mid=(l+r)/2;
if (mid>=pos) change(root*2,l,mid,Val,pos);
if (mid+1<=pos) change(root*2+1,mid+1,r,Val,pos);
sum[root]=sum[root<<1]+sum[root<<1|1];
}//不多讲,就是线段树
inline void dfs1(long long u,long long f)//u为当前点,f为父节点
{
long long e;
size[u]=1;//自己是自己子树的一个部分
fa[u]=f;//肯定的
dep[u]=dep[f]+1;//深度比父亲大1
for (long long e=first[u];e;e=next[e])//遍历所有与u相连的边
{
long long v=go[e];//此边到达的点
if (v==f) continue;//不能是父亲,要不然走上面回去了
dfs1(v,u);//让u当v的父亲再dfs
size[u]+=size[v];//子树u的size=dep[u]-1的所有直连子节点的子树size之和
if (size[v]>size[son[u]]) son[u]=v;//选出一个size最大的直连子节点做重儿子
}
}
inline void dfs2(long long u,long long f)
{
long long e;
if (son[u])//先走重儿子,使重路径在线段树中位置连续
{ //根在这无法赋值,要在主程序中赋值
seg[son[u]]=++seg[0];//seg[0]用于计数,将重儿子放到线段中
top[son[u]]=top[u];//父亲的重链顶端也是重儿子的重链顶端
rev[seg[0]]=son[u];//使线段树第x个位置对应树中的节点编号,rev[seg[x]]=x;
dfs2(son[u],u);//往重儿子处dfs
}
for (e=first[u];e;e=next[e])
{
long long v=go[e];
if (!top[v])//没有被遍历过,也就是不是u的重儿子或父亲
{
seg[v]=++seg[0];//同理,将v下放到线段中
rev[seg[0]]=v;//使线段树第x个位置对应树中的节点编号,rev[seg[x]]=x;
top[v]=v;//u,v为轻链,v定为重链开头,也就是top
dfs2(v,u);
}
}
}
inline void modify(long long root,long long maxl,long long maxr,long long l,long long r,long long v)
{
if (maxl>=l&&maxr<=r){Add[root]+=v;return;}
sum[root]+=(min(maxr,r)-max(maxl,l)+1)*v;
long long mid=(maxl+maxr)/2;
if (l<=mid) modify(root*2,maxl,mid,l,r,v);
if (mid<r) modify(root*2+1,mid+1,maxr,l,r,v);
}
inline void build(long long root,long long l,long long r)
{
long long mid=(l+r)/2;
if (l==r)
{
sum[root]=num[rev[l]];
return;
}
build(root<<1,l,mid);
build(root<<1|1,mid+1,r);
sum[root]=sum[root<<1]+sum[root<<1|1];
}//对着线段建树
long long tot=0;
inline void add(long long x,long long y)
{
next[++tot]=first[x];
go[tot]=y;
first[x]=tot;
}
inline void insert(long long x,long long y){add(x,y);add(y,x);}
inline void ask(long long x,long long y)
{
int fx=top[x],fy=top[y];
while(fx!=fy)
{
if (dep[fx]<dep[fy]) swap(x,y),swap(fx,fy);
SUMM+=query(1,1,seg[0],seg[fx],seg[x]);//这时的seg[0]也就成为了线段总长
SUMM%=p;
x=fa[fx]; fx=top[x];
}
if (dep[x]>dep[y]) swap(x,y);
SUMM+=query(1,1,seg[0],seg[x],seg[y]);//此时seg[x]为lca(x,y)
SUMM%=p;
}//LCA式路径询问
inline void updata(long long x,long long y,long long z)
{
int fx=top[x],fy=top[y];
while(fx!=fy)
{
if (dep[fx]<dep[fy]) swap(x,y),swap(fx,fy);
modify(1,1,seg[0],seg[fx],seg[x],z);//这时的seg[0]也就成为了线段总长
x=fa[fx]; fx=top[x];
}
if (dep[x]>dep[y]) swap(x,y);
modify(1,1,seg[0],seg[x],seg[y],z);//此时seg[x]为lca(x,y)
}//LCA式路径询问
inline long long read()
{
char chr;
long long f=1;
while (((chr=getchar())<'0')||(chr>'9')){if (chr=='-'){f=-1;}}
long long res=chr-'0';
while (((chr=getchar())>='0')&&(chr<='9')){res=res*10+chr-'0';}
return res*f;
}
void print(long long x)
{
if(x<0)putchar('-'),x=-x;
if(x>9)print(x/10);
putchar(x%10+'0');
}
int main()
{
//freopen("count1.in","r",stdin);
//freopen("count1.out","w",stdout);
n=read(); m=read(); r=read(); p=read();
for (long long i=1;i<=n;i++) num[i]=read();//点的权值
for (long long i=1;i<n;i++) insert(read(),read());//读入边
dfs1(r,r);//第一遍dfs，可找出fa,dep,size,son
seg[0]=seg[r]=1;
rev[1]=r;
top[r]=r;
dfs2(r,r);
build(1,1,seg[0]);
for (long long i=1;i<=m;i++)
{
SUMM=0;
long long kind=read();
if (kind==1)
{
long long x,y,z;
z%=p;
x=read();y=read();z=read();
updata(x,y,z);
}
if (kind==2)
{
long long x,y;
x=read();y=read();
ask(x,y);
print(SUMM%p);
putchar('\n');
}
else
{
if (kind==3)
{
long long x,y;
x=read();y=read();
y%=p;
modify(1,1,seg[0],seg[x],seg[x]+size[x]-1,y);
}
if (kind==4)
{
long long x;
x=read();
print(query(1,1,seg[0],seg[x],seg[x]+size[x]-1)%p);
putchar('\n');
}
}
}
return 0;
}
标记永久化线段树
#include<bits/stdc++.h>
#define Maxn 100005
#define LL long long
using namespace std;
inline void Read(LL &x)
{
LL f=1;x=0;char ch=getchar();
while (!isdigit(ch)){if (ch=='-') f=-1;ch=getchar();}
while (isdigit(ch)){x=x*10+ch-'0';ch=getchar();}
x*=f;
}
LL N,M,num[Maxn],id=0,rt,mark[Maxn*40];
struct node{LL ls,rs,sum;}tree[Maxn*40];
inline void build(LL &root,LL l,LL r)
{
if (!root) root=++id;
if (l==r) {tree[root].sum=num[l];return;}
LL mid=l+r>>1;
build(tree[root].ls,l,mid);
build(tree[root].rs,mid+1,r);
tree[root].sum=tree[tree[root].ls].sum+tree[tree[root].rs].sum;
}
inline void modify(LL root,LL l,LL r,LL ql,LL qr,LL x)
{
tree[root].sum+=(qr-ql+1)*x;
if (l==ql&&r==qr) {mark[root]+=x;return;}
LL mid=l+r>>1;
if (ql<=mid&&qr>mid) modify(tree[root].ls,l,mid,ql,mid,x),modify(tree[root].rs,mid+1,r,mid+1,qr,x);
if (qr<=mid) modify(tree[root].ls,l,mid,ql,qr,x);
if (ql>mid) modify(tree[root].rs,mid+1,r,ql,qr,x);
}
inline LL query(LL root,LL l,LL r,LL ql,LL qr,LL tag)
{
if (ql==l&&qr==r) {return tree[root].sum+tag*(r-l+1);}
LL mid=l+r>>1;
if (ql<=mid&&qr>mid) return query(tree[root].ls,l,mid,ql,mid,tag+mark[root])+query(tree[root].rs,mid+1,r,mid+1,qr,tag+mark[root]);
if (qr<=mid) return query(tree[root].ls,l,mid,ql,qr,tag+mark[root]);
if (ql>mid) return query(tree[root].rs,mid+1,r,ql,qr,tag+mark[root]);
}
int main()
{
Read(N),Read(M);
for (int i=1;i<=N;i++) Read(num[i]);
build(rt,1,N);
while (M--)
{
LL opt,x,y,k;
Read(opt);
if (opt==1)
{
Read(x),Read(y),Read(k);
modify(rt,1,N,x,y,k);
}
else
{
Read(x);Read(y);
cout<<query(rt,1,N,x,y,0)<<endl;
}
}
return 0;
}
中国剩余定理Crt
#include<bits/stdc++.h>
using namespace std;
long long n,b[15],w[15],ans=0,m=1,d,x,y;
void ex_gcd(long long a,long long b,long long d,long long &x,long long &y) {
if (b==0) x=1,y=0,d=a;
else
{
ex_gcd(b,a%b,d,x,y);
long long tmp=x;
x=y;
y=tmp-a/b*y;
}
}
void Crt() {
for (long long i=1; i<=n; i++) m*=w[i];
for (long long i=1; i<=n; i++)
{
long long u=m/w[i];
d=0;
x=0;
y=0;
ex_gcd(w[i],u,d,x,y);
ans=ans+y*u*b[i];
}
cout<<(ans%m+m)%m<<endl;
}
int main() {
scanf("%lld",&n);
for (long long i=1; i<=n; i++) scanf("%lld%lld",&b[i],&w[i]);
Crt();
return 0;
}
主席树
// luogu-judger-enable-o2
#include<bits/stdc++.h>
using namespace std;
int N,M,a[2000005],b[2000005],cnt,rt[8000005];
struct node{int sum,l,r;}T[8000005];
void build(int &root,int l,int r)
{
root=++cnt;
if (l==r) return;
int mid=(l+r)/2;
build(T[root].l,l,mid);
build(T[root].r,mid+1,r);
}
void update(int pre,int &root,int l,int r,int k)
{
root=++cnt;
T[root].l=T[pre].l;T[root].sum=T[pre].sum+1;T[root].r=T[pre].r;
if (l>=r) return;
int mid=(l+r)/2;
if (k<=mid) update(T[pre].l,T[root].l,l,mid,k);
else update(T[pre].r,T[root].r,mid+1,r,k);
}
int query(int x,int y,int l,int r,int k)
{
if (l>=r) return l;
int sum=T[T[y].l].sum-T[T[x].l].sum;
int mid=(l+r)/2;
if (k<=sum) return query(T[x].l,T[y].l,l,mid,k);
else return query(T[x].r,T[y].r,mid+1,r,k-sum);
}
int main()
{
memset(rt,0,sizeof(rt));
scanf("%d%d",&N,&M);
for (int i=1;i<=N;i++) scanf("%d",&a[i]),b[i]=a[i];
sort(b+1,b+N+1);
int tot=unique(b+1,b+N+1)-b-1;
build(rt[0],1,tot);
for (int i=1;i<=N;i++)
{
int x=lower_bound(b+1,b+tot+1,a[i])-b;
update(rt[i-1],rt[i],1,tot,x);
}
for (int i=1;i<=M;i++)
{
int x,y,z;
scanf("%d%d%d",&x,&y,&z);
cout<<b[query(rt[x-1],rt[y],1,tot,z)]<<endl;
}
return 0;
}
treap
#include<bits/stdc++.h>
#define MAXN 500005
using namespace std;
int tot,root,n;
struct node
{
int l,r,size,val,cnt,priority;
}tree[MAXN];
void updata(int x)//没讲,就是更新size值,可以讲,但没必要
{
tree[x].size=tree[tree[x].l].size+tree[x].cnt+tree[tree[x].r].size;
}
inline void rotate_right(int &x)
{
int y=tree[x].l;
tree[x].l=tree[y].r;
tree[y].r=x;
tree[y].size=tree[x].size;
updata(x);
x=y;
}
inline void rotate_left(int &x)
{
int y=tree[x].r;
tree[x].r=tree[y].l;
tree[y].l=x;
tree[y].size=tree[x].size;
updata(x);
x=y;
}
inline void insert(int &x,const int &num)//x是位置，num是插入值
{
if (!x)//插入
{
x=++tot; tree[x].val=num; tree[x].priority=rand();
tree[x].size=tree[x].cnt=1; tree[x].l=tree[x].r=0;
return;
}
else tree[x].size++;
//找地方插入
if (tree[x].val==num) tree[x].cnt++;//重复的话加cnt
else if (num<tree[x].val)//满足平衡树性质
{
insert(tree[x].l,num);
if (tree[tree[x].l].priority<tree[x].priority) rotate_right(x);//不满足小根堆性质，转一转
}
else
{
insert(tree[x].r,num);
if (tree[tree[x].r].priority<tree[x].priority) rotate_left(x);//不满足小根堆性质，转一转
}
}
inline void del(int &x,const int &num)
{
//删除
if (tree[x].val==num)
{
if (tree[x].cnt>1) tree[x].cnt--,tree[x].size--;//如果有重复就去个重就好了
else if (!tree[x].l||!tree[x].r) x=tree[x].l+tree[x].r;//如果叶节点不为2，那么就删掉此点连到唯一的叶节点上
else if (tree[tree[x].l].priority<tree[tree[x].r].priority) rotate_right(x),del(x,num);//左右儿子都有,先旋转再删除
else rotate_left(x),del(x,num);
return;
}
tree[x].size--;//儿子没了，爸爸大小肯定要减
//找地方删
if (num<tree[x].val) del(tree[x].l,num);
else del(tree[x].r,num);
return;
}
inline int before(const int &num)
{
int x=root,res=-2e9;
while (x)
{
if (tree[x].val<num) res=tree[x].val,x=tree[x].r;//比查询值小
else x=tree[x].l;
}
return res;
}
inline int after(const int &num)
{
int x=root,res=-2e9;
while (x)
{
if (tree[x].val>num) res=tree[x].val,x=tree[x].l;//比查询值大
else x=tree[x].r;
}
return res;
}
inline int kth(int k)
{
int x=root;
while (x)
{
if (tree[tree[x].l].size<k&&tree[tree[x].l].size+tree[x].cnt>=k) return tree[x].val;//x就是第k大
if (tree[tree[x].l].size>=k) x=tree[x].l;//x比第k大大，找左儿子
else k-=tree[tree[x].l].size+tree[x].cnt,x=tree[x].r;//x比第k大小，找右儿子，累加排名
}
return 0;
}
inline int rank(const int &num)
{
int x=root,res=0;
while (x)
{
if (num==tree[x].val) return res+tree[tree[x].l].size+1;
if (num<tree[x].val) x=tree[x].l;
else res+=tree[tree[x].l].size+tree[x].cnt,x=tree[x].r;
}
return res;
}
inline int read()
{
char chr;
int f=1;
while (((chr=getchar())<'0')||(chr>'9')){if (chr=='-'){f=-1;}}
int res=chr-'0';
while (((chr=getchar())>='0')&&(chr<='9')){res=res*10+chr-'0';}
return res*f;
}
inline void write(int x)
{
if(x<0) putchar('-'),x=-x;
if(x>9) write(x/10);
putchar(x%10+'0');
}
int main()
{
n=read();
for (int i=1;i<=n;i++)
{
int opt,x;
opt=read();x=read();
if (opt==1) insert(root,x);
if (opt==2) del(root,x);
if (opt==3) write(rank(x)),putchar('\n');
if (opt==4) write(kth(x)),putchar('\n');
if (opt==5) write(before(x)),putchar('\n');
if (opt==6) write(after(x)),putchar('\n');
}
return 0;
}
线段树合并
int merge(int x,int y)
{
if (!x) return y;
if (!y) return x;
k[x].l=merge(k[x].l,k[y].l);
k[x].r=merge(k[x].r,k[y].r);
k[x].sum=k[k[x].l].sum+k[k[x].r].sum;
return x;
}
可持久化trie
inline void insert(int pre,int &root,int i,int x)
{
root=++cnt;
t[root]=t[pre];
t[root].size++;
if (i<0) return;
if ((x>>i)&1) insert(t[pre].rs,t[root].rs,i-1,x);
else insert(t[pre].ls,t[root].ls,i-1,x);
}
inline int query(int pre,int root,int i,int x)
{
if (i<0) return 0;
if ((x>>i)&1)
{
if (t[t[root].ls].size-t[t[pre].ls].size>0) return query(t[pre].ls,t[root].ls,i-1,x)+(1<<i);
else return query(t[pre].rs,t[root].rs,i-1,x);
}
else
{
if (t[t[root].rs].size-t[t[pre].rs].size>0) return query(t[pre].rs,t[root].rs,i-1,x)+(1<<i);
else return query(t[pre].ls,t[root].ls,i-1,x);
}
}
FFT
#include<bits/stdc++.h>
#define Pi acos(-1.0)
#define Maxn 10000005
using namespace std;
inline int read()
{
int ret=0,f=1;char ch=getchar();
while(!isdigit(ch)){if(ch=='-') f=-f;ch=getchar();}
while(isdigit(ch)) ret=(ret<<1)+(ret<<3)+ch-'0',ch=getchar();
return ret*f;
}
struct node
{
double x,y;
friend inline node operator + (const node x,const node y){return (node){x.x+y.x,x.y+y.y};}
friend inline node operator - (const node x,const node y){return (node){x.x-y.x,x.y-y.y};}
friend inline node operator * (const node x,const node y){return (node){x.x*y.x-x.y*y.y,x.x*y.y+x.y*y.x};}
}a[Maxn];
int n,m,limit=1,r[Maxn],Log;
inline void FFT(node *A,int type)
{
for(int i=0;i<limit;i++) if(i<r[i]) swap(A[i],A[r[i]]);
for(int mid=1;mid<limit;mid<<=1){
node Wn=(node){cos(Pi/mid),type*sin(Pi/mid)};
for(int R=mid<<1,L=0;L<limit;L+=R)
{
node w=(node){1,0};
for(int k=0;k<mid;k++,w=w*Wn)
{
node x=A[L+k],y=w*A[L+mid+k];
A[L+k]=x+y,A[L+mid+k]=x-y;
}
}
}
}
int main()
{
n=read(),m=read();
for(int i=0;i<=n;i++) a[i].x=(double)read();for(int i=0;i<=m;i++) a[i].y=(double)read();
while(limit<=n+m) limit<<=1,Log++;for(int i=0;i<limit;i++) r[i]=(r[i>>1]>>1)|((i&1)<<(Log-1));
FFT(a,1);for(int i=0;i<limit;i++) a[i]=a[i]*a[i];FFT(a,-1);
for(int i=0;i<=n+m;i++) printf("%d ",(int)(a[i].y/(limit<<1)+0.5));
return 0;
}
Splay
#include<bits/stdc++.h>
#define LL long long
using namespace std;
inline void read(LL &x)
{
LL f=1;x=0;char ch=getchar();
while (!isdigit(ch)){if (ch=='-') f=-1;ch=getchar();}
while (isdigit(ch)){x=(x<<3)+(x<<1)+(ch&15);ch=getchar();}
x*=f;
}
LL n,m,rt,id=0;
struct tree{LL size,cnt,ch[2],fa,val;}t[1500005];
struct Splay
{
inline void update(LL x){t[x].size=t[t[x].ch[0]].size+t[t[x].ch[1]].size+t[x].cnt;}
inline LL identify(LL x){if (t[t[x].fa].ch[0]==x) return 0;if (t[t[x].fa].ch[1]==x) return 1;return -1;}
inline void connect(LL x,LL y,LL opt){t[x].fa=y;if (opt==-1) return;t[y].ch[opt]=x;}
inline void rotate(LL x){LL Fa=t[x].fa,FaFa=t[Fa].fa,optx=identify(x),opty=identify(Fa);connect(t[x].ch[optx^1],Fa,optx);connect(Fa,x,optx^1);connect(x,FaFa,opty);update(Fa),update(x);}
inline void splay(LL x,LL y)
{
while (t[x].fa!=y)
{
if (t[t[x].fa].fa!=y) if (identify(x)==identify(t[x].fa)) rotate(t[x].fa);else rotate(x);
rotate(x);
}
if (!y) rt=x;
}
inline void Find(LL x)
{
LL u=rt;
if (!u) return;
while (t[u].ch[x>t[u].val]&&x!=t[u].val) u=t[u].ch[x>t[u].val];
splay(u,0);
}
inline void insert(LL x)
{
LL u=rt,Fa=0;
while (u&&t[u].val!=x){Fa=u;u=t[u].ch[x>t[u].val];}
if (u) t[u].cnt++;
else{u=++id;if (Fa) t[Fa].ch[x>t[Fa].val]=u;t[u].ch[0]=t[u].ch[1]=0,t[u].fa=Fa,t[u].val=x,t[u].cnt=1,t[u].size=1;}
splay(u,0);
}
inline LL Pre(LL x)
{
Find(x);
LL u=t[rt].ch[0];
while (t[u].ch[1]) u=t[u].ch[1];
return u;
}
inline LL Aft(LL x){Find(x);LL u=t[rt].ch[1];while (t[u].ch[0]) u=t[u].ch[0];return u;}
inline void Delete(LL x)
{
LL Bef=Pre(x),Nex=Aft(x);splay(Bef,0),splay(Nex,rt);LL del_wz=t[t[rt].ch[1]].ch[0];
if (t[del_wz].cnt>1) {t[del_wz].cnt--;splay(del_wz,0);}else t[t[rt].ch[1]].ch[0]=0,t[t[t[rt].ch[1]].ch[0]].fa=0;
}
inline LL K_th(LL x)
{
LL u=rt;
if(t[u].size<x) return 0;
while(1){if(x>t[t[u].ch[0]].size+t[u].cnt) x-=t[t[u].ch[0]].size+t[u].cnt,u=t[u].ch[1];else{if(t[t[u].ch[0]].size>=x) u=t[u].ch[0];else return u;} }
}
}T;
int main()
{
LL lastans=0,Ans=0;
T.insert(-2147483647);
T.insert(2147483647);
read(n);read(m);
for (LL a,i=1;i<=n;i++) read(a),T.insert(a);
while(m--)
{
LL opt,x;
read(opt),read(x);
x^=lastans;
if(opt==1) T.insert(x);
if(opt==2) T.Delete(x);
if(opt==3) T.insert(x),T.Find(x),lastans=t[t[rt].ch[0]].size,T.Delete(x),Ans^=lastans;
if(opt==4) lastans=t[T.K_th(x+1)].val,Ans^=lastans;
if(opt==5) T.insert(x),lastans=t[T.Pre(x)].val,T.Delete(x),Ans^=lastans;
if(opt==6) T.insert(x),lastans=t[T.Aft(x)].val,T.Delete(x),Ans^=lastans;
}
cout<<Ans<<endl;
return 0;
}
LCT
#include<bits/stdc++.h>
#define LL long long
using namespace std;
LL n,m;
inline void read(LL &x){LL f=1;x=0;char ch=getchar();while (!isdigit(ch)){if (ch=='-') f=-1;ch=getchar();}while (isdigit(ch)){x=(x<<3)+(x<<1)+(ch&15);ch=getchar();}x*=f;}
struct LCT
{
struct tree{LL ch[2],fa,val,sum,tag;}t[1000005];
inline LL identify(LL x){if (t[t[x].fa].ch[0]==x) return 0;if (t[t[x].fa].ch[1]==x) return 1;return -1;}
inline void connect(LL x,LL y,LL opt){t[x].fa=y;if (opt==-1) return;t[y].ch[opt]=x;}
inline void pushup(LL x){t[x].sum=t[t[x].ch[0]].sum^t[t[x].ch[1]].sum^t[x].val;}
inline void pushdown(LL x){if(t[x].tag){swap(t[x].ch[0],t[x].ch[1]);t[t[x].ch[0]].tag^=1;t[t[x].ch[1]].tag^=1;t[x].tag=0;}}
inline void pushall(LL x){if(identify(x)!=-1)pushall(t[x].fa);pushdown(x);}
inline void rotate(LL x){LL Fa=t[x].fa,FaFa=t[Fa].fa,optx=identify(x),opty=identify(Fa);connect(t[x].ch[optx^1],Fa,optx);connect(Fa,x,optx^1);connect(x,FaFa,opty);pushup(Fa),pushup(x);}
inline void splay(LL x){pushall(x);while (identify(x)!=-1){if (identify(t[x].fa)!=-1){if (identify(x)==identify(t[x].fa)) rotate(t[x].fa);else rotate(x);}rotate(x);}}
inline void access(LL x){LL las=0;while (x){splay(x);t[x].ch[1]=las;pushup(x);las=x;x=t[x].fa;}}
inline void make_root(LL x){access(x),splay(x),t[x].tag^=1,pushdown(x);}
inline void split(LL x,LL y){make_root(x);access(y);splay(y);}
inline LL findroot(LL x){access(x);splay(x);while(t[x].ch[0]){pushdown(x);x=t[x].ch[0];}splay(x);return x;}
inline void link(LL x,LL y){make_root(x);if(findroot(y)==x)return;t[x].fa=y;}
inline void cut(LL x,LL y){if(findroot(x)!=findroot(y))return;split(x,y);if(t[x].fa!=y||t[x].ch[1])return;t[x].fa=t[y].ch[0]=0;pushup(x);}
}T;
int main()
{
read(n),read(m);
for (LL i=1;i<=n;i++) read(T.t[i].val),T.t[i].sum=T.t[i].val;
while (m--)
{
LL opt,x,y;
read(opt),read(x),read(y);
if (opt==0) T.split(x,y),cout<<T.t[y].sum<<endl;
if (opt==1) T.link(x,y);
if (opt==2) T.cut(x,y);
if (opt==3) T.splay(x),T.t[x].val=y;
}
return 0;
}