香蕉公司
题意：维护 \(n\) 的排列 \(a_0\) 与 \(p\)。\(q\) 次操作，交换 \(a_0\) 中两个值或 \(p\) 中两个值，或者比较 \(a_x\) 与 \(a_y\) 的字典序大小，其中 \(a_{k,i}=a_{k-1,p_i}\)。
\(n,q\le10^5\)，\(x,y\le10^{18}\)。
称 \(a_x\) 与 \(a_y\) 第一次不相同的点为关键点。
显然维护置换环。可以用平衡树维护还上的顺序，然后注意到一个环上的编号最小点才有可能成为关键点。所以以每个环上最小点为下标建立线段树，维护的是环的大小的 \(\text{lcm}\)。那么查找时直接线段树上二分出关键点再检查即可。
由于代码能力很弱，所以感到十分有成就感，于是把代码贴出来。
code1
#include<bits/stdc++.h>
using namespace std;
const int N=100005;
int n,q,a[N];
inline long long lcm(long long x,long long y) {
long long g=__gcd(x,y);
__int128 res=(__int128)x*y/g;
if (res>1e18) res=1e18+1;
return res;
}
namespace SegmentTree {
long long dat[N<<2];
inline void pushup(int p) {
dat[p]=lcm(dat[p<<1],dat[p<<1|1]);
return;
}
void upd(int p,int l,int r,int x,long long d) {
if (l==r) {
dat[p]=d;
return;
}
int mid=(l+r)>>1;
if (x<=mid) upd(p<<1,l,mid,x,d);
else upd(p<<1|1,mid+1,r,x,d);
pushup(p);
return;
}
long long get(int p,int l,int r,long long k,long long L) {
if (l==r) {
if (l==n&&k%lcm(L,dat[p])==0) return n+1;
return l;
}
int mid=(l+r)>>1;
long long Lcm=lcm(dat[p<<1],L);
if (k%Lcm==0) return get(p<<1|1,mid+1,r,k,Lcm);
return get(p<<1,l,mid,k,L);
}
}
using namespace SegmentTree;
namespace SplayTree {
struct Node {
int fa,siz,dat,ch[2];
}tr[N];
inline void update(int x) {
tr[x].siz=tr[tr[x].ch[0]].siz+tr[tr[x].ch[1]].siz+1;
tr[x].dat=min(x,min(tr[tr[x].ch[0]].dat,tr[tr[x].ch[1]].dat));
return;
}
inline void rotate(int x) {
int y=tr[x].fa;
int z=tr[y].fa;
if (z) tr[z].ch[tr[z].ch[1]==y]=x;
tr[x].fa=z;
int pos=tr[y].ch[1]==x;
tr[y].ch[pos]=tr[x].ch[pos^1];
if (tr[x].ch[pos^1]) tr[tr[x].ch[pos^1]].fa=y;
tr[x].ch[pos^1]=y,tr[y].fa=x;
update(y);
update(x);
return;
}
inline void splay(int x,int fa) {
while (tr[x].fa!=fa) {
int y=tr[x].fa;
int z=tr[y].fa;
if (z!=fa) {
if ((tr[z].ch[1]==y)^(tr[y].ch[1]==x)) rotate(x);
else rotate(y);
}
rotate(x);
}
return;
}
inline bool check(int x,int y) {
splay(x,0);
splay(y,0);
return (tr[y].ch[0]==x)|(tr[y].ch[1]==x)|(tr[tr[y].ch[0]].ch[0]==x)|(tr[tr[y].ch[0]].ch[1]==x)|(tr[tr[y].ch[1]].ch[0]==x)|(tr[tr[y].ch[1]].ch[1]==x);
}
inline void split(int l,int r) {
splay(l,0);
upd(1,1,n,tr[l].dat,1);
splay(r,l);
upd(1,1,n,tr[tr[r].ch[0]].dat,tr[tr[r].ch[0]].siz);
tr[tr[r].ch[0]].fa=0;
tr[r].ch[0]=0;
update(r);
update(l);
splay(r,0);
upd(1,1,n,tr[r].dat,tr[r].siz);
return;
}
inline int getrnk(int x) {
splay(x,0);
return tr[tr[x].ch[0]].siz+1;
}
inline int getkth(int x,int k) {
while (1) {
if (tr[tr[x].ch[0]].siz+1==k) {
splay(x,0);
return x;
}
if (tr[tr[x].ch[0]].siz>=k) x=tr[x].ch[0];
else k-=tr[tr[x].ch[0]].siz+1,x=tr[x].ch[1];
}
}
}
using namespace SplayTree;
int main() {
tr[0].dat=1e9;
for (int i=1;i<N*4;i++) dat[i]=1;
scanf("%d %d",&n,&q);
for (int i=1;i<=n;i++) tr[i].siz=1,tr[i].dat=i,a[i]=i;
for (int i=1;i<=q;i++) {
int opt;
long long x,y;
scanf("%d %lld %lld",&opt,&x,&y);
if (opt==1) {
swap(a[x],a[y]);
} else if (opt==2) {
if (x==y) continue;
if (check(x,y)) {
int res1=getrnk(x),res2=getrnk(y),siz=tr[y].siz;
if (res1>res2) swap(x,y),swap(res1,res2);
if (res2==siz) {
splay(x,0);
upd(1,1,n,tr[x].dat,1);
int z=getkth(x,res1+1);
splay(x,z);
tr[x].fa=0;
tr[z].ch[0]=0;
update(z);
upd(1,1,n,tr[x].dat,tr[x].siz);
upd(1,1,n,tr[z].dat,tr[z].siz);
} else {
splay(y,0);
int res=getkth(y,res2+1);
split(x,res);
}
} else {
upd(1,1,n,tr[x].dat,1);
upd(1,1,n,tr[y].dat,1);
int res1=getrnk(x),res2=getrnk(y);
if (res2!=tr[y].siz) {
int siz=tr[y].siz;
int t=getkth(y,res2+1);
int z=getkth(t,siz);
int w=getkth(z,1);
splay(t,0);
splay(y,t);
tr[tr[t].ch[0]].fa=0;
tr[t].ch[0]=0;
update(t);
splay(z,0);
splay(w,0);
tr[z].ch[1]=w;
tr[w].fa=z;
update(z);
}
if (res1==tr[x].siz) {
splay(y,0);
tr[x].ch[1]=y;
tr[y].fa=x;
update(x);
upd(1,1,n,tr[x].dat,tr[x].siz);
splay(y,0);
} else {
int r=getkth(x,res1+1);
splay(x,0);
splay(r,x);
splay(y,0);
tr[r].ch[0]=y;
tr[y].fa=r;
update(r);
update(x);
splay(r,0);
upd(1,1,n,tr[r].dat,tr[r].siz);
}
}
} else {
int flag=0;
x--,y--;
if (x<y) swap(x,y),flag=1;
int res=get(1,1,n,x-y,1);
if (res==n+1) {
puts("=");
continue;
}
int pos=getrnk(res);
int siz=tr[res].siz;
int f1=getkth(res,(pos+x-1)%siz+1);
int f2=getkth(f1,(pos+y-1)%siz+1);
if ((a[f1]<a[f2])^flag) puts("<");
else puts(">");
}
}
return 0;
}
奶牛
题意：无向连通图有 ABC 三类点。将某些 C 点删掉，使得所有 A 类点互相可达，且任何 AB 点对互不可达。记删掉的点集为 \(S\)，A 类点点集为 \(T\)，构造一种删除方案，使得 \(\max\limits_{x\in S}\{\min\limits_{y\in T}\{d(x,y)\}\}\) 最小，其中 \(d(x,y)\) 表示 \(x\) 和 \(y\) 在原图中的距离。
\(1\le n,m\le3\times10^5\)。
考虑二分需要最小化的值。那么可以处理出来能够删除的点。设它们为 D 类点，设删不了的 C 类为 E 类。那么很显然如果将所有 D 类删掉后都有 A 和 B 连通显然不可行否则考虑贪心：将所有 AD 块与 BE 块交界处的 D 类点删掉。这样是尽可能保证 A 类互相连通的。
虽然但是，一堆 ABCDE 类好阴间。
退役的你
题意：给定一个整数集 \(S\)，构造一个大小为 \(k\) 的整数集 \(T\)，使得其中元素都属于 \([1,2^{30}-1]\) 并且最大化 \(\sum\limits_{x\in T}\sum\limits_{y\in S}[x\&y=y]\)，其中 \(\&\) 表示按位与。
\(1\le k\le10^3\)，\(S_i\in[1,2^{30}-1]\)，\(1\le|S|\le5\times10^5\)。
我们考虑当 \(a\&b=b\)，那么 \(a\) 一定是优于 \(b\) 的。所以我们每次加入当前贡献最大的元素后，只需要将其任一 \(1\) 位变成 \(0\)，加入候选集合。用优先队列维护即可，初始是 \(2^{30}-1\)。然而我们计算贡献的复杂度是 \(O(n)\) 的，考虑优化。事实上，用 bitset 来维护对于每一位，该位置是 \(1\) 的 \(S\) 中元素，转移贡献就直接在 bitset 上操作一次即可。这样复杂度就降低了。
P4497
链接。
这个题的数据好像有不只一种合法解，所以按照出题人的意愿，差分数组为 0 的应该跟负数一起处理。
我们可以贪心地考虑到若 \(k\) 为奇数，则 \(B_k<B_{k+1}\)。所以题目可以转化为在差分序列上选择若干段和为正数的值，最后的值就是选出数的和，那么显然选且仅选正数是最优的。这是易于维护的。
考虑第二问，实质上就是在差分序列中，两段正数中间的负数段上选一个数删掉，然后加上其他负数。那么删最大值最优。所以对每个负数段 \(S\)，记 \(f_S=\sum\limits_{x\in S}x-\max\limits_{x\in S}\{x\}\)，那么用 set 维护连续负数段，用权值线段树维护 \(f\)，查询的时候直接在权值线段树上二分即可。
显然包含开头或末尾的连续负数段不能产生贡献，另外注意差分序列在 \(2\) 到 \(n\) 的范围内考虑。
什么？又是 ds？看来又要贴代码了。
code2
#include<bits/stdc++.h>
using namespace std;
const int N=100005;
const long long lim=2e10;
int T,n,q;
long long a[N],d[N],sum;
namespace SegmentTree {
long long dat1[N<<2],dat2[N<<2];
int cnt,root;
struct P {
long long dat;
int sum,lc,rc;
}tr[N*105];
void upd(int p,int l,int r,int x,long long d) {
if (l==r) {
dat1[p]=dat2[p]=d;
return;
}
int mid=(l+r)>>1;
if (x<=mid) upd(p<<1,l,mid,x,d);
else upd(p<<1|1,mid+1,r,x,d);
dat1[p]=dat1[p<<1]+dat1[p<<1|1];
dat2[p]=max(dat2[p<<1],dat2[p<<1|1]);
return;
}
long long getsum(int p,int l,int r,int L,int R) {
if (L<=l&&r<=R) return dat1[p];
int mid=(l+r)>>1;
long long res=0;
if (L<=mid) res+=getsum(p<<1,l,mid,L,R);
if (R>mid) res+=getsum(p<<1|1,mid+1,r,L,R);
return res;
}
long long getmax(int p,int l,int r,int L,int R) {
if (L<=l&&r<=R) return dat2[p];
int mid=(l+r)>>1;
long long res=-1e18;
if (L<=mid) res=max(res,getmax(p<<1,l,mid,L,R));
if (R>mid) res=max(res,getmax(p<<1|1,mid+1,r,L,R));
return res;
}
void insert(int&p,long long l,long long r,long long x,int d) {
if (!p) p=++cnt;
if (l==r) {
tr[p].dat+=x*d;
tr[p].sum+=d;
return;
}
long long mid=(l+r)>>1ll;
if (-x<=mid) insert(tr[p].lc,l,mid,x,d);
else insert(tr[p].rc,mid+1,r,x,d);
tr[p].dat=tr[tr[p].lc].dat+tr[tr[p].rc].dat;
tr[p].sum=tr[tr[p].lc].sum+tr[tr[p].rc].sum;
return;
}
int getans(int p,long long l,long long r,long long k) {
if (l==r) return (int)((k+l-1)/l);
long long mid=(l+r)>>1ll,Rdat=tr[tr[p].rc].dat;
int Rsum=tr[tr[p].rc].sum;
if (-Rdat>=k) return getans(tr[p].rc,mid+1,r,k);
return Rsum+getans(tr[p].lc,l,mid,k+Rdat);
}
}
using namespace SegmentTree;
typedef pair<int,int> pai;
set<pai>s;
inline long long get(int l,int r) {
if (l==2||r==n) return 0;
return getsum(1,2,n,l,r)-getmax(1,2,n,l,r);
}
inline void add(int pos,int x) {
if (pos==1||pos>n) return;
if (d[pos]>0) sum-=d[pos];
d[pos]+=x;
if (d[pos]>0) sum+=d[pos];
if (d[pos]-x<=0) {
auto it=s.lower_bound(pai(pos,pos));
if (it==s.end()) it--;
else if ((*it).first>pos) it--;
int l=(*it).first,r=(*it).second;
insert(root,0,lim,get(l,r),-1);
upd(1,2,n,pos,d[pos]);
if (d[pos]>0) {
s.erase(it);
if (pos>l) s.insert(pai(l,pos-1)),insert(root,0,lim,get(l,pos-1),1);
if (pos<r) s.insert(pai(pos+1,r)),insert(root,0,lim,get(pos+1,r),1);
} else {
insert(root,0,lim,get(l,r),1);
}
} else if (d[pos]<=0) {
int L=pos,R=pos;
if (pos-1>1&&d[pos-1]<=0) {
auto it=s.lower_bound(pai(pos-1,pos-1));
if (it==s.end()) it--;
else if ((*it).first>pos-1) it--;
int l=(*it).first,r=(*it).second;
s.erase(it);
insert(root,0,lim,get(l,r),-1);
L=l;
}
if (pos+1<=n&&d[pos+1]<=0) {
auto it=s.lower_bound(pai(pos+1,pos+1));
int l=(*it).first,r=(*it).second;
s.erase(it);
insert(root,0,lim,get(l,r),-1);
R=r;
}
upd(1,2,n,pos,d[pos]);
s.insert(pai(L,R));
insert(root,0,lim,get(L,R),1);
} else upd(1,2,n,pos,d[pos]);
return;
}
int main() {
scanf("%d",&T);
while (T--) {
s.clear();
memset(dat1,0,sizeof dat1);
memset(dat2,0,sizeof dat2);
for (int i=1;i<=cnt;i++) tr[i].lc=tr[i].rc=tr[i].dat=tr[i].sum=0;
root=cnt=1;
scanf("%d %d",&n,&q);
for (int i=1;i<=n;i++) {
scanf("%lld",&a[i]);
d[i]=a[i]-a[i-1];
}
sum=0;
int lst=0;
for (int i=2;i<=n;i++) {
if (d[i]>0) {
if (lst) {
s.insert(pai(lst,i-1));
lst=0;
}
sum+=d[i];
} else {
if (!lst) lst=i;
}
upd(1,2,n,i,d[i]);
}
if (lst) s.insert(pai(lst,n));
for (auto x:s) {
int l=x.first,r=x.second;
insert(root,0,lim,get(l,r),1);
}
for (int i=1;i<=q;i++) {
int opt,l,r,c;
scanf("%d",&opt);
if (opt) {
printf("%lld ",sum);
if (sum+tr[root].dat>0) puts("-1");
else {
printf("%d\n",getans(root,0,lim,sum));
}
} else {
scanf("%d %d %d",&l,&r,&c);
add(l,c);
add(r+1,-c);
}
}
}
return 0;
}
光与影
题意：给定一颗 splay 的当前形态，然后随机选择一个点将其 splay 到根，问每个点的期望深度。
\(1\le n\le10^6\)。
场切了。但是其实不难，就是分类讨论然后暴力树形 dp。主要是贴个代码。感受一下动态规划的丑陋。
code3
#include<bits/stdc++.h>
using namespace std;
inline int read(){
int f=0,x=0;
char ch=getchar();
while(!isdigit(ch)){f|=(ch=='-');ch=getchar();}
while(isdigit(ch)){x=x*10+ch-'0';ch=getchar();}
return f?-x:x;
}
const int N=1000005,mod=1000000007;
int n,ch[N][2],fa[N],st[N],ed[N],tot,dep[N],rnk[N],pre[N][2];
long long dp[N][2],ans[N];
inline int get(int x) {
if (!x) return 0;
return pre[ed[x]][dep[x]&1]-pre[st[x]-1][dep[x]&1];
}
void dfs0(int p,int d,int lst) {
dep[p]=d,fa[p]=lst;
st[p]=++tot,rnk[tot]=p;
if (ch[p][0]) dfs0(ch[p][0],d+1,p);
if (ch[p][1]) dfs0(ch[p][1],d+1,p);
ed[p]=tot;
return;
}
void dfs(int p,long long f) {
ans[p]+=f;
ans[p]+=dep[p];
if (p!=1) {
if (fa[p]==1) {
int pos=ch[fa[p]][1]==p;
dp[p][pos]=1;
} else {
int y=fa[p];
int z=fa[y];
int pos1=ch[y][1]==p;
int pos2=ch[z][1]==y;
if (pos1==pos2) {
dp[p][pos1]=dp[z][pos1]+2;
dp[p][pos1^1]=dp[z][pos1^1]+1;
} else {
dp[p][pos1]=dp[z][pos1]+1;
dp[p][pos1^1]=dp[z][pos1^1]+1;
}
}
}
int pos=ch[fa[p]][1]==p;
ans[p]+=(dp[p][1]-2)*get(ch[ch[p][0]][0]);
ans[p]+=(dp[p][0]-2)*get(ch[ch[p][1]][1]);
ans[p]+=(dp[p][1]-1)*get(ch[ch[p][0]][1]);
ans[p]+=(dp[p][0]-1)*get(ch[ch[p][1]][0]);
if (p==1) {
ans[p]-=get(ch[p][0]);
ans[p]-=get(ch[p][1]);
} else {
ans[p]+=dp[fa[p]][0]*get(ch[p][1]);
ans[p]+=dp[fa[p]][1]*get(ch[p][0]);
}
if (ch[p][0]) {
long long F=f;
F+=dp[p][0];
F+=(dp[p][0]-2)*get(ch[ch[p][1]][1]);
F+=(dp[p][0]-1)*get(ch[ch[p][1]][0]);
if (pos==1||p==1) {
F+=(dp[fa[p]][0]-1)*get(ch[p][1]);
} else {
F+=dp[fa[p]][0]*get(ch[p][1]);
}
dfs(ch[p][0],F);
}
if (ch[p][1]) {
long long F=f;
F+=dp[p][1];
F+=(dp[p][1]-2)*get(ch[ch[p][0]][0]);
F+=(dp[p][1]-1)*get(ch[ch[p][0]][1]);
if (pos==0||p==1) {
F+=(dp[fa[p]][1]-1)*get(ch[p][0]);
} else {
F+=dp[fa[p]][1]*get(ch[p][0]);
}
dfs(ch[p][1],F);
}
return;
}
int main() {
n=read();
for (int i=1;i<=n;i++) ch[i][0]=read(),ch[i][1]=read();
dfs0(1,0,0);
for (int i=1;i<=n;i++) {
pre[i][0]=pre[i-1][0];
pre[i][1]=pre[i-1][1];
pre[i][dep[rnk[i]]&1]++;
}
dfs(1,0);
long long res=0;
for (int i=1;i<=n;i++) {
res=1ll*n*dep[i]-ans[i];
printf("%lld\n",res%mod);
}
return 0;
}
彩树
给定简单无向图 \(G=\{E,V\}\)，每个节点有一个颜色，颜色总数为 \(k\)。求有多少个子图 \(H\) 满足其中每个点的颜色互不相同，且一共 \(k\) 个点，并且是一棵树。
\(1\le|E|\le200\)，\(1\le k\le12\)。
记 \(|E|\) 为 \(n\)。我们可以考虑求有根树的数量，最后除以 \(k\)。然后状压即可。令 \(f_{i,S}\) 表示根为 \(i\)，已选颜色集合为 \(S\) 的方案数，那么可以枚举与它相邻的点进行转移。为了避免算重，可以钦定一个添加子树顺序。但是发现这种做法是 \(O(3^kn^2)\) 的，考虑优化。实际上枚举相邻的点这一步比较多余，可以边算边预处理。时间复杂度 \(O(3^kn)\)。