终于把 agc 交了。
A. Jagged Swaps
模拟即可。
B. AB Flipping
显然全是 \(\texttt{B}\) 的前缀和全是 \(\texttt{A}\) 的后缀都动不了。
答案是最后一个 \(\texttt{B}\) 的位置减第一个 \(\texttt{A}\) 的位置。
WA 了一发，真服了 /oh。
C. Matching Arrays
先把 \(a,b\) 分别升序排序，然后把 \(b\) 的最后 \(x\) 个位置移到开头。
如果有解这样一定合法。
D. Ones and Twos
原题：P6859 蝴蝶与花，[POI2011] LIZ-Lollipop （不带修）。
突破口肯定是序列只有 \(1\) 和 \(2\)，在这上面找找性质。
先把明显无解的询问排除掉（比如大于 \([1,n]\) 的区间和），考虑什么情况下会无解：存在一个区间 \([l,r]\) 使得 \(sum(l,r)=x-1\)，且 \(a_{r+1}=2\)。这样区间和就会把 \(x\) 恰好跳过去。
进一步地，可以证明：如果 \(x-1\) 无解，那么 \(x\) 一定有解；\(x\) 无解当且仅当 \(x-1\) 的所有解后面紧跟着的数都是 \(2\)（或为序列结尾）。
考虑先二分找到一个合法的区间 \(sum(1,l)=x-1\)，将它向右移动，要保证每移动一次区间的开头结尾都依然是 \(2\)。这个限制本质上是 \([1,n-l]\cup[l+1,n]\) 里面没有 \(1\)。
树状数组维护一下即可。单 \(\log\) 做法就是把二分的过程换成线段树二分，不过两 \(\log\) 甚至能跑过上面两个 \(n=2\times 10^6\) 的原题，所以摆了。
下面代码的时间复杂度是 \(\mathcal{O}(n\log^2n)\)。
Code
const int N=2e5+5;
int T,n,q,a[N];
struct BIT
{
int tr[N];
il void clear() {for(int i=1;i<=n;i++) tr[i]=0;}
il void add(int x,int k) {for(;x<=n;x+=x&(-x)) tr[x]+=k;}
il int query(int x) {int res=0;for(;x;x-=x&(-x)) res+=tr[x];return res;}
il int ask(int l,int r) {return query(r)-query(l-1);}
}tr;
int main()
{
T=read();
while(T--)
{
n=read(),q=read(); tr.clear();
for(int i=1;i<=n;i++) a[i]=read(),tr.add(i,a[i]);
while(q--)
{
int op=read(),x=read();
if(op==2)
{
int v=read();
int now=tr.ask(x,x);
tr.add(x,v-now);
continue;
}
if(x==1)
{
if(tr.ask(1,n)==2*n) printf("NO\n");
else printf("YES\n");
continue;
}
int l=0,r=n;
while(l<r)
{
int mid=(l+r+1)>>1;
if(tr.ask(1,mid)<=x-1) l=mid;
else r=mid-1;
}
if(l!=n&&tr.ask(1,l+1)==x) {printf("YES\n");continue;}
if(tr.ask(1,l)!=x-1) {printf("NO\n");continue;}
if(tr.ask(1,n-l)!=2*(n-l)||tr.ask(l+1,n)!=2*(n-l)) printf("YES\n");
else printf("NO\n");
}
}
return 0;
}
E. Permutation Sorting
设 \(pos_i\) 表示数 \(i\) 在 \(a\) 序列里的位置。
将 \(pos_i\) 向 \(i\) 连边，一次操作就相当于让所有边的起点移到最近的下一个不是自环的点。
考虑连向 \(i\) 的边的起点 \(u\) 移到 \(j\) 的时候 \(j\) 是不是自环，其实就是比较 \(pos_i\) 和 \(pos_j\) 谁离 \(j\) 更近。设 \(dis(x,y)\) 表示不考虑自环，\(x\) 移动到 \(y\) 的距离。
那么进一步考虑总贡献，\(pos_i\) 移到 \(i\) 的过程中跳过的自环数就是 \(dis(pos_j,j)<dis(pos_i,j)\) 的 \(j\) 的个数。
左边那一半对于每个 \(j\) 来说是定值，右边根据 \(j\) 和 \(pos_i\) 的位置关系分类讨论一下是个公差为 \(1\) 的等差数列。
那么问题就是对于给定的序列 \(c_i=dis(pos_i,i)\)，令 \(b_{l,\dots,r}=x,x+1,\dots,x+r-l+1\)，求 \(\sum\limits_{i=l}^r [c_i < b_i]\)。把定义改为 \(c_i=dis(pos_i,i)-i\)，二维数点即可。
Code
const int N=2e6+5;
int T,n,a[N],pos[N],dis[N],ans[N];
struct node{int k,tp,id;};
vector<node> q[N];
il void add(int l,int r,int x,int id) {q[l-1].push_back({x-(l),-1,id}),q[r].push_back({x-(l),1,id});}
struct BIT
{
int tr[N];
il void clear() {for(int i=1;i<=n+n+1;i++) tr[i]=0;}
il void add(int x,int k) {for(;x<=n+n+1;x+=x&(-x)) tr[x]+=k;}
il int query(int x) {int res=0;for(;x;x-=x&(-x)) res+=tr[x];return res;}
il int ask(int l,int r) {return query(r)-query(l-1);}
}tr;
void solve()
{
for(int i=1;i<=n;i++)
{
tr.add(dis[i]-(i)+n+1,1);
for(auto x:q[i]) ans[x.id]+=x.tp*tr.ask(x.k+n+1,n+n+1);
}
for(int i=0;i<=n;i++) q[i].clear();
}
int main()
{
T=read();
while(T--)
{
n=read(); tr.clear();
for(int i=1;i<=n;i++) ans[i]=0;
for(int i=1;i<=n;i++) a[i]=read(),pos[a[i]]=i;
for(int i=1;i<=n;i++) dis[i]=(i>=pos[i])?i-pos[i]:(n+i-pos[i]);
for(int i=1;i<=n;i++)
{
int x=pos[i],ans=0;
if(pos[i]<=i) add(pos[i],i-1,0,i);
else add(pos[i],n,0,i),add(1,i-1,n-pos[i]+1,i);
}
solve();
for(int i=1;i<=n;i++) printf("%d ",ans[i]);
printf("\n");
}
return 0;
}
F. Bracket Xoring
Description
给定一个长度为 \(2n\) 的 \(\texttt{01}\) 串 \(s\)。一次操作定义为：
- 选择一个长度为 \(2n\) 的合法括号串（所有括号均匹配）；
- 对于每个左括号，设它的位置为 \(l\)，与它匹配的右括号位置为 \(r\)，将 \(s\) 的 \([l,r]\) 这个区间取反（\(\texttt{0}\) 变成 \(\texttt{1}\)，\(\texttt{1}\) 变成 \(\texttt{0}\)）。
请构造方案在 \(10\) 次操作内将 \(s\) 的所有位置变为 \(\texttt{0}\)，并输出方案。
多组数据，\(T\le 10^3\)，\(\sum n\le 2\times 10^5\)。
Solution
先找一些比较容易直接看出来的性质。
- 每次操作都一定会改变 \(s_1\) 和 \(s_{2n}\)，故 \(s_1\neq s_{2n}\) 无解；
- 每次操作都会取反偶数个位置，故 \(s\) 中有奇数个 \(1\) 无解。
注意到只要这个字符串满足 \(\forall i\bmod 2=0,s_i=s_{i+1}\)（不含首尾），就可以用一次操作让整个字符串变成一样的。
先假设这里的 \(s_1=\texttt{1}\)，如果不是可以先做一次 \(\texttt{()()...()}\) 操作将整个串取反。
具体地，从开头开始令每两个相邻的 \(\texttt{1}\) 配成一对括号，显然这些括号位置的取反次数都是 \(1\)；每两个相邻的 \(\texttt{1}\) 之间一定有偶数个 \(\texttt{0}\)，我们把它们两两配对成 \(\texttt{()()...}\) 的形式，那么它们因为包含在一组 \(\texttt{1}\) 形成的括号内，均不会被取反。
例如 \(s=\texttt{1000011001}\)，则构造操作 \(\texttt{(()())(())}\)。
所以我们如果能构造一些前置操作使字符串满足这个条件就做完了。
考虑对于一个任意的串，怎么让 \(s_i\) 和 \(s_{i+1}\) 相等：
- 若本身就 \(s_i=s_{i+1}\)，在这里放一对 \(\texttt{()}\)，那么这两位的取反状态一定是一样的；
- 否则要么放两个左括号要么放两个右括号，我们根据前面未匹配的括号数判断：如果有未匹配的括号（显然这不会是一个奇数），在这里放 \(\texttt{))}\)，否则放 \(\texttt{((}\)。
第二种情况一定出现偶数次（否则不满足有偶数个 \(1\)），所以这样构造出的括号串一定是匹配的。
综上，我们至多使用三步操作使 \(s\) 全为 \(0\)。
写代码的时候精神状态堪忧，可能和上面讲的没什么关系。（upd: 重写了。）
Code
const int N=4e5+5;
int T,n,a[N],b[N],c[N];
char s[N];
int main()
{
T=read();
while(T--)
{
n=read()<<1; scanf("%s",s+1);
for(int i=1;i<=n;i++) a[i]=s[i]-'0';
int cnt=0; for(int i=1;i<=n;i++) cnt+=a[i];
if(a[1]!=a[n]||(cnt&1)) {printf("-1\n");continue;}
if(a[1])
{
printf("3\n");
for(int i=1;i<=n;i++) a[i]^=1,printf(i&1?"(":")"); printf("\n");
}
else printf("2\n");
int sum=0; a[1]^=1,a[n]^=1;
printf("(");
for(int i=2;i<n;i+=2)
{
if(a[i]==a[i+1]) printf("()");
else if(!sum) printf("(("),a[i+1]^=1,sum^=1;
else printf("))"),a[i]^=1,sum^=1;
}
printf(")\n(");
for(int i=2;i<n;i+=2) printf(a[i]?")(":"()");
printf(")\n");
}
return 0;
}