A. k-Amazing Numbers
略
B. Make Them Equal
略
C. XOR Inverse
略
D. Graph and Queries
处理仅含删边的图连通性问题，可以离线后倒着处理，转化为仅含加边的图连通性问题，可以简单地用并查集维护。不仅如此，我们还可以尝试对连通块的合并建出一个有根树森林，其中叶子节点是初始时的点，每次合并两个连通块新建一个点作为它们的共同父亲即可。这样，任意时刻某个连通块对应的点集对应某个子树，若我们只维护真实的节点，可以理解为dfs序上一段区间。
这样问题就比较简单了。我们再正着扫一遍处理询问，对dfs序用一棵线段树维护区间最大值，每次询问即为找出区间最大值并做单点修改。
时间复杂度为O((n+m+q)log?n)\mathcal O((n+m+q)\log n)O((n+m+q)logn)。
#include <bits/stdc++.h>
#define last last2
#define inf 0x3f3f3f3f
#define lowbit(x) (x&-x)
#define FR first
#define SE secondusing namespace std;typedef long long ll;
typedef pair<int,int> pr;namespace SETS {
int fa[500005];void init(int n) {
for(int i=1;i<=n;i++) fa[i]=i;
}int find_father(int x) {
return (fa[x]==x)?x:fa[x]=find_father(fa[x]);
}bool check(int x,int y) {
x=find_father(x);y=find_father(y);return x!=y;
}void merge(int x,int y) {
x=find_father(x);y=find_father(y);if (x==y) return;fa[x]=y;
}}int num[500005],bel[500005],pos[500005];namespace SGT {
int maxn[2000000];inline void pushup(int o) {
if (num[maxn[o*2]]>=num[maxn[o*2+1]]) maxn[o]=maxn[o*2];else maxn[o]=maxn[o*2+1];
}void build(int l,int r,int o) {
if (l==r) maxn[o]=bel[l];else {
int m=((l+r)>>1);build(l,m,o*2);build(m+1,r,o*2+1);pushup(o);}
}void update(int l,int r,int o,int p) {
if (l==r) return;else {
int m=((l+r)>>1);if (m>=p) update(l,m,o*2,p);else update(m+1,r,o*2+1,p);pushup(o);}
}int query(int l,int r,int o,int lx,int rx) {
if (l>=lx&&r<=rx) return maxn[o];else {
int m=((l+r)>>1);if (m>=rx) return query(l,m,o*2,lx,rx);if (m<lx) return query(m+1,r,o*2+1,lx,rx);int a=query(l,m,o*2,lx,rx),b=query(m+1,r,o*2+1,lx,rx);return (num[a]>=num[b])?a:b;}
}}int ch[1000005][2],dfn[1000005],ed[1000005],dfs_cnt,n;void dfs(int x) {
dfn[x]=dfs_cnt+1;if (x<=n) bel[++dfs_cnt]=x;if (ch[x][0]) dfs(ch[x][0]);if (ch[x][1]) dfs(ch[x][1]);ed[x]=dfs_cnt;
}pr a[500005],e[500005];
bool vis[500005];
int rt[500005],id[500005],sz;void merge(int x,int y) {
x=SETS::find_father(x);y=SETS::find_father(y);if (x==y) return;SETS::merge(x,y);sz++;ch[sz][0]=rt[x];ch[sz][1]=rt[y];rt[SETS::find_father(x)]=sz;
}int main() {
int m,k;scanf("%d%d%d",&n,&m,&k);for(int i=1;i<=n;i++) scanf("%d",&num[i]);for(int i=1;i<=m;i++) scanf("%d%d",&e[i].FR,&e[i].SE);for(int i=1;i<=k;i++) {
int x,y;scanf("%d%d",&x,&y);a[i]=pr(x,y);if (x==2) vis[y]=1;}SETS::init(n);for(int i=1;i<=n;i++) rt[i]=i;sz=n;for(int i=1;i<=m;i++)if (!vis[i]) merge(e[i].FR,e[i].SE);for(int i=k;i>0;i--)if (a[i].FR==1) id[i]=rt[SETS::find_father(a[i].SE)];else merge(e[a[i].SE].FR,e[a[i].SE].SE);for(int i=1;i<=n;i++)if (SETS::find_father(i)==i) dfs(rt[i]);SGT::build(1,n,1);for(int i=1;i<=k;i++)if (a[i].FR==1) {
int x=id[i];int v=SGT::query(1,n,1,dfn[x],ed[x]);printf("%d\n",num[v]);num[v]=0;SGT::update(1,n,1,dfn[v]);}return 0;
}
E. Split
可以将问题转化为最大化bi=bi+1b_i=b_{i+1}bi?=bi+1?的对数。
首先考虑一个暴力的DP。令fi,jf_{i,j}fi,j?仅考虑b1?b2ib_1\sim b_{2i}b1??b2i?，且b2i=jb_{2i}=jb2i?=j的最大值，这里有1≤j<ai1\leq j<a_i1≤j<ai?，转移是容易的。
容易发现对于某个iii，令max?j=1?ai?1fi,j=pi\max_{j=1\sim a_i-1}f_{i,j}=p_imaxj=1?ai??1?fi,j?=pi?，显然只有那些fi,j=pif_{i,j}=p_ifi,j?=pi?的jjj是有用的（否则假设最优解中前2i2i2i个的f<pif<p_if<pi?，那么直接取某个fi,j=pif_{i,j}=p_ifi,j?=pi?的，将后面设为与最优解中相同，这样一定不会变劣）。
那么我们可以考虑记录下pip_ipi?，并且只维护满足fi,j=pif_{i,j}=p_ifi,j?=pi?的jjj组成的集合SiS_iSi?。转移的时候我们可能会将SiS_iSi?中的元素xxx变为ai+1?xa_{i+1}-xai+1??x，或是删除<1<1<1的xxx，或是单点插入，随后分类讨论一下pi+1p_{i+1}pi+1?即可。显然SiS_iSi?中的极大连续段（区间）只有O(n)\mathcal O(n)O(n)个，我们可以用set维护这些区间，每次暴力删除越界的区间。转移的时候要涉及将xxx变为ai?xa_i-xai??x，比较简单的方式是打一个整体修改的标记，这样不需要特别的处理。
单组数据时间复杂度为O(nlog?n)\mathcal O(n\log n)O(nlogn)。
#include <bits/stdc++.h>
#define last last2
#define inf 0x3f3f3f3f3f3f3f3fLL
#define lowbit(x) (x&-x)
#define FR first
#define SE secondusing namespace std;typedef long long ll;
typedef pair<ll,ll> pr;set <pr> st;
ll v,c;void pop() {
if (v==1) {
while (!st.empty()) {
set<pr>::iterator it=st.begin();if ((it->SE)+c>0) break;else {
pr t=*it;st.erase(it);if (t.FR+c>0) {
st.insert(pr(t.FR,1-c));break;}}}}else {
while (!st.empty()) {
set<pr>::iterator it=st.end();it--;if (-(it->FR)+c>0) break;else {
pr t=*it;st.erase(it);if (-t.SE+c>0) {
st.insert(pr(c-1,t.SE));break;}}}}
}bool find(int k) {
if (st.empty()) return 0;if (v==1) {
set<pr>::iterator it=st.lower_bound(pr(k-c,-inf));if (it!=st.end()&&(it->SE)<=k-c) return 1;else return 0;}else {
set<pr>::iterator it=st.lower_bound(pr(c-k,-inf));if (it!=st.end()&&(it->SE)<=c-k) return 1;else return 0;}
}void insert(int k) {
if (v==1) st.insert(pr(k-c,k-c));else st.insert(pr(c-k,c-k));
}int num[500005];int main() {
int cases;scanf("%d",&cases);for(;cases;cases--) {
st.clear();v=1;c=0;int n;scanf("%d",&n);for(int i=1;i<=n;i++) scanf("%d",&num[i]);int ans=2*n;if (num[1]%2==0) {
ans--;st.insert(pr(num[1]>>1,num[1]>>1));}else st.insert(pr(num[1]-1,1));for(int i=2;i<=n;i++) {
v=-v;c=num[i]-c;pop();if (num[i]%2==0) {
if (find(num[i]>>1)) {
ans-=2;v=1;c=0;st.clear();st.insert(pr(num[i]>>1,num[i]>>1));}else {
ans-=1;insert(num[i]>>1);}}else if (!st.empty()) ans-=1;else {
v=1;c=0;st.clear();st.insert(pr(num[i]-1,1));}}printf("%d\n",ans);}return 0;
}
F. Showing Off
令最终的矩阵为AAA。
容易发现按题目中的方式，最终形成的有向图一定是一个基环内向树森林，且每个环的长度都是偶数，环上所有的aaa都相同，还要满足这个aaa至少是环长，且不在环上的点一定满足父亲的aaa小于自己的aaa。进一步可以发现，对于一个长度>2>2>2的偶环我们可以任取一个相邻点的匹配，匹配的点之间互相连边，这样就只有长为222的环了，那么aaa一定不小于环长。
这样问题就比较简单了。可以发现一个点一定不可能连向aaa大于它的点，因此我们可以对aaa从小到大构造。每次设当前还没有确定父亲的点中最小的aaa是k≥2k\geq 2k≥2，我们考虑a=ka=ka=k的点的集合SSS，确定这些点的出边。那么对于某个x∈Sx\in Sx∈S，它可能跟另一个相邻的y∈Sy\in Sy∈S匹配成一个长为222的环，或是连向某个相邻的满足a<ka<ka<k的点zzz。
注意到这是一个网格图，一定是二分图。那么对SSS中点黑白染色后，容易建出一个上下界网络流模型：令源点为SSS，汇点为TTT，对于某个黑点xxx，连边(S,x)(S,x)(S,x)，上下界均为111，且若它与某个a<ka<ka<k的点zzz相邻，连边(x,T)(x,T)(x,T)，下界为000，上界为111；对于某个黑点yyy，连边(y,T)(y,T)(y,T)，上下界均为111，且若它与某个a<ka<ka<k的点zzz相邻，连边(S,y)(S,y)(S,y)，下界为000，上界为111；若xxx与yyy相邻，额外连边(x,y)(x,y)(x,y)，下界为000，上界为111。那么若该上下界网络流没有可行解显然原问题无解，否则容易根据得到的可行流构造方案。
我们构出的的图总点数和边数都是O(nm)\mathcal O(nm)O(nm)级别的，且这是个单位权图，直接跑dinic算法单组数据时间复杂度为O(nmnm)\mathcal O(nm\sqrt{nm})O(nmnm?)。
#include <bits/stdc++.h>
#define last last2
#define inf 0x3f3f3f3f
#define lowbit(x) (x&-x)
#define FR first
#define SE secondusing namespace std;typedef long long ll;
typedef pair<int,int> pr;struct Edge {
int t,f,next;Edge() {
}Edge(int a,int b,int c):t(a),f(b),next(c) {
}
};Edge e[5000000];
int head[100010],vs,vt,tot;inline void addEdge(int x,int y,int z) {
e[++tot]=Edge(y,z,head[x]);head[x]=tot;e[++tot]=Edge(x,0,head[y]);head[y]=tot;
}namespace Flow {
int d[100010],cur[100010];
queue <int> q;bool bfs() {
while (!q.empty()) q.pop();for(int i=vs;i<=vt;i++) d[i]=-1;d[vs]=0;cur[vs]=head[vs];q.push(vs);while (!q.empty()) {
int x=q.front();q.pop();for(int i=head[x];i!=-1;i=e[i].next)if (e[i].f&&d[e[i].t]==-1) {
int u=e[i].t;d[u]=d[x]+1;cur[u]=head[u];if (u==vt) return 1;q.push(u);}}return 0;
}int dfs(int x,int a) {
if (x==vt||!a) return a;int ans=0;for(int &i=cur[x];i!=-1;i=e[i].next)if (e[i].f&&d[e[i].t]==d[x]+1) {
int u=e[i].t;int f=dfs(u,min(a,e[i].f));if (f) {
e[i].f-=f;e[i^1].f+=f;ans+=f;a-=f;if (!a) break;}}return ans;
}int maxflow() {
int ans=0;while (bfs())ans+=dfs(vs,inf);return ans;
}}int *num[100005],*id[100005],*ans1[100005];
char *ans2[100005];pr a[100005];bool solve(int n,int m,int k,int val) {
vs=0;vt=k+3;tot=-1;for(int i=vs;i<=vt;i++) head[i]=-1;int sz1=0,sz2=0;for(int i=1;i<=k;i++) id[a[i].FR][a[i].SE]=i;for(int i=1;i<=k;i++) {
int x=a[i].FR,y=a[i].SE;if (!((x^y)&1)) {
sz1++;addEdge(vs,i,1);bool v=0;if (x>1) {
if (num[x-1][y]<val) v=1;else if (num[x-1][y]==val) addEdge(id[x][y],id[x-1][y],1);}if (x<n) {
if (num[x+1][y]<val) v=1;else if (num[x+1][y]==val) addEdge(id[x][y],id[x+1][y],1);}if (y>1) {
if (num[x][y-1]<val) v=1;else if (num[x][y-1]==val) addEdge(id[x][y],id[x][y-1],1);}if (y<m) {
if (num[x][y+1]<val) v=1;else if (num[x][y+1]==val) addEdge(id[x][y],id[x][y+1],1);}if (v) addEdge(i,k+2,1);}else {
sz2++;addEdge(i,vt,1);bool v=0;if (x>1&&num[x-1][y]<val) v=1;if (x<n&&num[x+1][y]<val) v=1;if (y>1&&num[x][y-1]<val) v=1;if (y<m&&num[x][y+1]<val) v=1;if (v) addEdge(k+1,i,1);}}addEdge(k+2,k+1,inf);addEdge(k+1,vt,sz1);addEdge(vs,k+2,sz2);if (Flow::maxflow()<sz1+sz2) return 0;for(int i=1;i<=k;i++) {
int x=a[i].FR,y=a[i].SE;if (!((x^y)&1)) {
for(int j=head[i];j!=-1;j=e[j].next)if (e[j].t==k+2&&!e[j].f) {
if (x>1&&num[x-1][y]<val) {
ans1[x][y]=val-num[x-1][y];ans2[x][y]='U';}else if (x<n&&num[x+1][y]<val) {
ans1[x][y]=val-num[x+1][y];ans2[x][y]='D';}else if (y>1&&num[x][y-1]<val) {
ans1[x][y]=val-num[x][y-1];ans2[x][y]='L';}else if (y<m&&num[x][y+1]<val) {
ans1[x][y]=val-num[x][y+1];ans2[x][y]='R';}}else if (e[j].t>=1&&e[j].t<=k&&!e[j].f) {
int u=a[e[j].t].FR,v=a[e[j].t].SE;ans1[x][y]=1;ans1[u][v]=val-1;if (u==x-1) {
ans2[x][y]='U';ans2[u][v]='D';}else if (u==x+1) {
ans2[x][y]='D';ans2[u][v]='U';}else if (v==y-1) {
ans2[x][y]='L';ans2[u][v]='R';}else if (v==y+1) {
ans2[x][y]='R';ans2[u][v]='L';}}}else {
for(int j=head[i];j!=-1;j=e[j].next)if (e[j].t==k+1&&e[j].f) {
if (x>1&&num[x-1][y]<val) {
ans1[x][y]=val-num[x-1][y];ans2[x][y]='U';}else if (x<n&&num[x+1][y]<val) {
ans1[x][y]=val-num[x+1][y];ans2[x][y]='D';}else if (y>1&&num[x][y-1]<val) {
ans1[x][y]=val-num[x][y-1];ans2[x][y]='L';}else if (y<m&&num[x][y+1]<val) {
ans1[x][y]=val-num[x][y+1];ans2[x][y]='R';}}}}return 1;
}bool cmp(pr x,pr y) {
return num[x.FR][x.SE]<num[y.FR][y.SE];
}pr b[100005];int main() {
int cases;scanf("%d",&cases);for(;cases;cases--) {
int n,m;scanf("%d%d",&n,&m);for(int i=0;i<=n+1;i++) {
num[i]=new int[m+2];id[i]=new int[m+2];ans1[i]=new int[m+2];ans2[i]=new char[m+2];memset(num[i],0,sizeof(int)*(m+2));memset(id[i],0,sizeof(int)*(m+2));memset(ans1[i],0,sizeof(int)*(m+2));memset(ans2[i],0,sizeof(char)*(m+2));}int sz=0;for(int i=1;i<=n;i++)for(int j=1;j<=m;j++) {
scanf("%d",&num[i][j]);b[++sz]=pr(i,j);}sort(b+1,b+sz+1,cmp);bool v=1;for(int i=1,j=1;i<=sz;i=j+1) {
while (j<sz&&num[b[i].FR][b[i].SE]==num[b[j+1].FR][b[j+1].SE]) j++;int sz2=0;for(int k=i;k<=j;k++) a[++sz2]=b[k];if (!solve(n,m,sz2,num[b[i].FR][b[i].SE])) {
v=0;break;}} if (!v) puts("NO");else {
puts("YES");for(int i=1;i<=n;i++) {
for(int j=1;j<=m;j++) printf("%d ",ans1[i][j]);printf("\n");}for(int i=1;i<=n;i++) {
for(int j=1;j<=m;j++) printf("%c ",ans2[i][j]);printf("\n");}}}return 0;
}