（这比赛挺智障的……但是我更智障就是了）
$T1$：
题意：
给定两个序列A,B，有m个操作，形如：
- $(1,i,j)$，效果是将$A_{i},A_{j}$同时+1或-1。
- $(2,i,j)$，效果是将$A_{i},A_{j}$一个+1一个-1。
你可以任意进行操作，问是否能将A变成B。
$nleq 10^{5}$。
题解：
感觉是三题里面最难想的一个题……
首先如果只有2操作，那么直接并查集一下，每个连通块权值和相等就可以变过去，否则不行。
现在新增了一些1操作，那么先按2缩一下点，再按1连边。
连完之后画一下，发现一条长度为偶数的路径可以把这上面的点权随意增减和重新分配。
那么也就是说如果一个连通块有奇环，它就一定满足条件。
如果没有奇环那么是一个二分图，显然可以在满足左右点权差不变的情况下重新分配点权。
以上条件均为充要条件，于是就做完了。
复杂度$O(n)$。
代码：
#include<bits/stdc++.h> #define maxn 1000005 #define maxm 500005 #define inf 0x7fffffff #define ll long long #define rint register int #define debug(x) cerr<<#x<<": "<<x<<endl #define fgx cerr<<"--------------"<<endl #define dgx cerr<<"=============="<<endl using namespace std; int n,op,col[maxn],A[maxn],sum[maxn],sm[2],tot[2],e[3][maxn][2]; int f[maxn],vis[maxn],hd[maxn],to[maxn<<1],nxt[maxn<<1],cnt; inline int read(){ int x=0,f=1; char c=getchar(); for(;!isdigit(c);c=getchar()) if(c=='-') f=-1; for(;isdigit(c);c=getchar()) x=x*10+c-'0'; return x*f; } inline int find(int x){return f[x]==x?x:f[x]=find(f[x]);} inline void addedge(int u,int v){ to[++cnt]=v,nxt[cnt]=hd[u],hd[u]=cnt; to[++cnt]=u,nxt[cnt]=hd[v],hd[v]=cnt; } inline void dfs(int u,int c){ //cout<<u<<":"<<sum[u]<<endl; vis[u]=1,col[u]=c,sm[c]+=sum[u]; for(int i=hd[u];i;i=nxt[i]){ int v=to[i]; if(!vis[v]) dfs(v,c^1); else if(col[v]==col[u]) op=1; } return; } int main(){ int T=read(); while(T--){ memset(col,0,sizeof(col)); memset(hd,0,sizeof(hd)); memset(vis,0,sizeof(vis)); cnt=0,tot[0]=tot[1]=0; int n=read(),m=read(); for(int i=1;i<=n;i++) A[i]=read(); for(int i=1;i<=n;i++) A[i]-=read(); for(int i=1;i<=m;i++){ int t=read()-1; e[t][++tot[t]][0]=read(); e[t][tot[t]][1]=read(); } //cout<<tot[0]<<" "<<tot[1]<<endl; for(int i=1;i<=n;i++) f[i]=i,sum[i]=A[i]; for(int i=1;i<=tot[1];i++){ int u=e[1][i][0],v=e[1][i][1]; int t1=find(u),t2=find(v); if(t1!=t2) f[t2]=t1,sum[t1]+=sum[t2]; } for(int i=1;i<=tot[0];i++){ int u=e[0][i][0],v=e[0][i][1]; //cout<<find(u)<<" "<<find(v)<<endl; addedge(find(u),find(v)); } bool flag=0; for(int i=1;i<=n;i++){ int u=find(i); if(!vis[u]){ op=sm[0]=sm[1]=0,dfs(u,0); //cout<<sm[0]<<" "<<sm[1]<<endl; if(op && (sm[0]+sm[1])%2!=0){printf("NO "),flag=1;break;} if(!op && sm[0]!=sm[1]){printf("NO "),flag=1;break;} } } if(!flag) printf("YES "); } return 0; }
$T2$：
题意：
有一个1-n的排列，m次操作或询问。
每次操作会交换位置x和x+1的数，每次询问将该排列冒泡排序k次后的逆序对个数。
$n,mleq 2 imes 10^{5}$。
题解：
设$f(i)$为以i为右端点的逆序对个数。那么每次操作就是$f(i)$整体减一并左移，满足$f(i)$非负。
然后发现每次操作就是交换一下两个$f(i)$并使某一个+1或-1，于是直接拿个树状数组维护一下即可。
复杂度$O(nlogn)$，不知道我咋写错了。
代码：
#include<bits/stdc++.h> #define maxn 200005 #define maxm 500005 #define inf 0x7fffffff #define ll long long #define rint register ll #define debug(x) cerr<<#x<<": "<<x<<endl #define fgx cerr<<"--------------"<<endl #define dgx cerr<<"=============="<<endl using namespace std; ll n,m,a0,s1[maxn],s2[maxn],A[maxn],P[maxn],num[maxn],C[maxn]; inline ll read(){ ll x=0,f=1; char c=getchar(); for(;!isdigit(c);c=getchar()) if(c=='-') f=-1; for(;isdigit(c);c=getchar()) x=x*10+c-'0'; return x*f; } inline void add(ll x){for(ll i=x;i<=n;i+=(i&(-i)))C[i]++;} inline ll qry(ll x){ll ans=0;for(ll i=x;i;i-=(i&(-i)))ans+=C[i];return ans;} inline void add1(ll x,ll y){for(ll i=x;i<=n;i+=(i&(-i)))s1[i]+=y;} inline ll qry1(ll x){ll ans=0;for(ll i=x;i;i-=(i&(-i)))ans+=s1[i];return ans;} inline void add2(ll x,ll y){for(ll i=x;i<=n;i+=(i&(-i)))s2[i]+=y;} inline ll qry2(ll x){ll ans=0;for(ll i=x;i;i-=(i&(-i)))ans+=s2[i];return ans;} inline void init(){ for(ll i=1;i<=n;i++) add(P[i]),num[i]=qry(n)-qry(P[i]); //for(ll i=1;i<=n;i++) cout<<num[i]<<" ";cout<<endl; for(ll i=1;i<=n;i++) A[num[i]]++; for(ll i=1;i<=n;i++) a0+=A[i]*i,add1(i,A[i]),add2(i,A[i]*i); } inline void del(ll x){A[x]--,a0-=x,add1(x,-1),add2(x,-x);} inline void ins(ll x){A[x]++,a0+=x,add1(x,1),add2(x,x);} int main(){ n=read(),m=read(); for(ll i=1;i<=n;i++) P[i]=read(); init(); while(m--){ ll t=read(); if(t==1){ ll x=read(); if(num[x]) del(num[x]); if(num[x+1]) del(num[x+1]); (P[x]<P[x+1])?(num[x]++):(num[x+1]--); swap(P[x],P[x+1]),swap(num[x],num[x+1]); if(num[x]) ins(num[x]); if(num[x+1]) ins(num[x+1]); } else{ ll k=min(read(),n); if(k==0) printf("%lld ",a0); else printf("%lld ",a0-k*qry1(n)+k*qry1(k)-qry2(k)); } } return 0; }
$T3$：
题意：
有一个长度为n的序列组成的环，m次询问。
每次给定一个k，你需要重新排列这个环上的数，使得环上任意两个距离为k的数字乘积之和最大，并输出这个值。
$n,mleq 2 imes 10^{5}$。
题解：
观察一下可以发现共有$gcd(n,k)$个互不相关的环。
根据均值不等式之类的性质可以猜出“大的放一个环，小的放一个环”是最优解，每个环里放成三角形最优。
那么直接模拟一下，由于答案只和$frac{n}{gcd(n,k)}$有关，那么最多有$sqrt{n}$个不同的答案。
复杂度$O(msqrt{n})$。
代码：
#include<bits/stdc++.h> #define maxn 200005 #define maxm 500005 #define inf 0x7fffffff #define ll long long #define rint register ll #define debug(x) cerr<<#x<<": "<<x<<endl #define fgx cerr<<"--------------"<<endl #define dgx cerr<<"=============="<<endl using namespace std; ll n,m,A[maxn],ans[maxn]; inline ll read(){ ll x=0,f=1; char c=getchar(); for(;!isdigit(c);c=getchar()) if(c=='-') f=-1; for(;isdigit(c);c=getchar()) x=x*10+c-'0'; return x*f; } inline bool cmp(ll x,ll y){return x>y;} inline ll gcd(ll x,ll y){return y==0?x:gcd(y,x%y);} inline ll calc(ll t){ ll res=0; //cout<<t<<endl; for(ll i=1;i<=n;i+=(n/t)){ for(ll j=i;j<=i+(n/t)-3;j++) res+=A[j]*A[j+2]; res+=A[i]*A[i+1]+A[i+(n/t)-1]*A[i+(n/t)-2]; } return res; } int main(){ n=read(),m=read(); ll sum=0; for(ll i=1;i<=n;i++) A[i]=read(),sum+=A[i]*A[i]; sort(A+1,A+n+1,cmp); while(m--){ ll k=read(),t=gcd(n,k); if(!k){printf("%lld ",sum);continue;} if(!ans[t]) ans[t]=calc(t); printf("%lld ",ans[t]); } return 0; }