Reverse
题目背景
小\(\text{G}\)有一个长度为\(n\)的\(01\)串\(T\)，其中只有\(T_S=1\)，其余位置都是\(0\)。现在小\(\text{G}\)可以进行若干次以下操作：
• 选择一个长度为\(K\)的连续子串（\(K\)是给定的常数），翻转这个子串。
对于每个\(i,i\in [1,n]\)，小\(\text{G}\)想知道最少要进行多少次操作使得\(T_i=1\).特别的，有\(m\)个“禁止位置”，你需要保证在操作过程中\(1\)始终不在任何一个禁止位置上。
输入输出格式
输入格式
从文件reverse.in中读入数据.
第一行四个整数\(n,K,m,S\).
接下来一行\(m\)个整数表示禁止位置。
输出格式
输出到文件reverse.out中.
输出一行\(n\)个整数，对于第\(i\)个整数，如果可以通过若干次操作使得\(T_i=1\)，输出最小操作次数，否则输出\(-1\).
说明
对于所有数据，有\(1≤n≤10^5,1≤S,k≤n,0≤m≤n\).
保证\(S\)不是禁止位置，但禁止位置可能有重复。
\(\text{Subtask1}(24\%), n≤10\).
\(\text{Subtask2}(22\%), n≤10^3\).
\(\text{Subtask3}(3\%), k=1\).
\(\text{Subtask4}(8\%), k=2\).
\(\text{Subtask5}(43\%)\), 没有特殊的约束。
题目其实并不难
发现可以连边直接bfs，可以拿到57pts的暴力分
发现边的数量很多，需要支持动态删点
用两颗平衡树分别维护位置为奇数时和位置为偶数时
然后每次找到可翻转的左边和右边，在平衡上二分，bfs然后删掉点就可以了
每个点只会被删掉一次，复制度差不多是\(O(nlogn)\)的
Code:
#include <cstdio>
#include <cstring>
#include <set>
const int N=1e5+10;
std::set <int> s1,s2;
std::set <int>::iterator it;
int n,k,m,s,l=1,r,q[N<<2],used[N],ans[N],lp,rp,d;
int min(int x,int y){return x<y?x:y;}
int max(int x,int y){return x>y?x:y;}
int main()
{
scanf("%d%d%d%d",&n,&k,&m,&s);
memset(ans,-1,sizeof(ans));
used[s]=1,q[++r]=s,ans[s]=0;
for(int p,i=1;i<=m;i++) scanf("%d",&p),used[p]=1;
for(int i=1;i<=n;i+=2)
{
if(!used[i]) s1.insert(i);
if(!used[i+1]) s2.insert(i+1);
}
while(l<=r)
{
int p=q[l++];
lp=max(p-k+1,max(k-p+1,1)),rp=min(p+k-1,min(2*n+1-k-p,n));
if(p-k&1)//s2
{
it=s2.lower_bound(lp);
while(it!=s2.end()&&(d=*it)<=rp)
{
q[++r]=d;
ans[d]=ans[p]+1;
it++;
s2.erase(d);
}
}
else
{
it=s1.lower_bound(lp);
while(it!=s1.end()&&(d=*it)<=rp)
{
q[++r]=d;
ans[d]=ans[p]+1;
it++;
s1.erase(d);
}
}
}
for(int i=1;i<=n;i++)
printf("%d ",ans[i]);
return 0;
}
2018.10.7