YZOJ P3389 [FOI 2018 四校联训 Round 3]消息密匙
时间限制：3000MS 内存限制：131072KB
难度：\(6.0\)
-
题目描述
已知密匙与一个长度为 \(n\) 的字符串有关，字符串中的字符都来自于字符集 \(\{\text{‘a’..}\text{‘z’}, \text{‘?’}\}\)，每个 \(\text{‘?’}\) 的位置都要被填上一个小写字母，我们定义一个填好的串是合法的当且仅当它满足如下条件：
在输入的 \(m\) 次操作后与这个串操作之前的样子相比没有改变。
一次操作是翻转这个串的第 \(l_i\) 个字符到第 \(r_i\) 个字符。
求出字典序第 \(K\) 小的合法的能被填出的串，因为密码就是它。
-
输入格式
第一行三个数 \(n,m,k\) 。
第二行一个长度为 \(n\) 的串。
接下来 \(m\) 行每行两个数 \(l_i\) 和 \(r_i\) 。
-
输出格式
一个串，表示字典序第 \(K\) 小的合法的能被填出的串。
-
样例输入
|
1 2 3 |
12 1 4 ztrs?a?isred 5 7 |
-
样例输出
|
1 |
ztrsdadisred |
-
数据规模与约定
对于 \(100\%\) 的数据，保证 \(n,m \leq 5 \times 10^5, k \leq 1 \times 10^{18}\) 。
首先把每个 \(\text{‘?’}\) 变成一个 \(>26\) 的数字编号，然后序列翻转使用平衡树（Treap，Splay，pb_ds等）维护。
如果原串或新串中有的字符不为 \(\text{‘?’}\) ，那么就可以直接确定这一位上的字母。
如果都为 \(\text{‘?’}\) 的话，就用并查集把它们并起来。
最后，一个连通块内的字母一定是相同的。
因为有字典序的限制，所以并查集并的时候注意编号小的作为根节点。
字典序 \(K\) 大怎么求？把它 \(26\) 进制分解，一个个连通块按编号从小到大分配即可。
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 101 102 103 104 105 106 107 108 109 110 111 112 113 114 115 116 117 118 119 120 121 122 123 124 125 126 127 128 129 130 131 132 133 134 135 136 137 138 139 140 141 142 143 144 145 146 147 148 149 150 151 152 153 154 155 156 157 158 159 160 161 162 163 164 165 166 167 168 169 170 171 172 173 174 175 176 177 178 179 180 181 182 183 184 185 186 187 188 189 190 191 192 193 194 195 196 197 198 199 200 201 202 203 204 205 206 207 208 209 210 211 212 213 |
#include <cstdio> #include <cstdlib> #include <cstring> #include <climits> #include <ctime> #define _min(_a_,_b_) ((_a_)<(_b_)?(_a_):(_b_)) #define _max(_a_,_b_) ((_a_)>(_b_)?(_a_):(_b_)) template<class T> inline T getnum() { register char c=0; while(!(c>='0' && c<='9')) c=getchar(); register T a=0; while(c>='0' && c<='9') { a*=10,a+=c-'0'; c=getchar(); } return a; } inline void getstr(int s[],int&lq) { lq=26; register char c=0; while(!((c>='a' && c<='z') || c=='?')) c=getchar(); register int ls=0; while((c>='a' && c<='z') || c=='?') { s[++ls]=c-'a'+1; if(c=='?') s[ls]=++lq; c=getchar(); } s[ls+1]=0; return; } int uf[501010]; int UnionFind(register int x) { if(x == uf[x]) return x; return uf[x]=UnionFind(uf[x]); } inline void UnionMerge(register int x,register int y) { register int fx=UnionFind(x),fy=UnionFind(y); if(fx != fy) uf[_max(fx,fy)]=_min(fx,fy); } int s[501010],os[501010]; int qval[501010]; unsigned _seed,_ret; #define rnd() (_ret=_seed,_seed=_seed*7+23,_ret) #pragma GCC optimize(3) int root,cnt,size[501010],lson[501010],rson[501010],pri[501010]; bool rev[501010]; inline int CreateNode() { size[++cnt]=1; pri[cnt]=rnd(); return cnt; } inline void PushUp(register int x) { size[x]=size[lson[x]]+size[rson[x]]+1; } inline void PushDown(register int x) { rev[x]^=1; lson[x]^=rson[x]^=lson[x]^=rson[x]; rev[lson[x]]^=1,rev[rson[x]]^=1; } inline int MergeTree(register int x,register int y) { if(!x || !y) return x^y; if(rev[x]) PushDown(x); if(rev[y]) PushDown(y); if(pri[x] < pri[y]) { rson[x]=MergeTree(rson[x],y); return PushUp(x),x; } else { lson[y]=MergeTree(x,lson[y]); return PushUp(y),y; } } inline void SplitTreeByOrder(register int o,register int k,int&x,int&y) { if(!o) { x=y=0; return; } if(rev[o]) PushDown(o); if(k <= size[lson[o]]) y=o,SplitTreeByOrder(lson[o],k,x,lson[o]); else x=o,SplitTreeByOrder(rson[o],k-size[lson[o]]-1,rson[o],y); PushUp(o); } inline int BuildTree(register int l,register int r) { static int stk[501010]; register int top=0; for(register int i=l;i<=r;i++) { register int x=CreateNode(),last=0; while(top && pri[stk[top]] > pri[x]) PushUp(stk[top]),last=stk[top],stk[top--]=0; if(top) rson[stk[top]]=x; lson[x]=last,stk[++top]=x; } while(top) PushUp(stk[top--]); return stk[1]; } int _tls; void PrintTree(register int o) { if(rev[o]) PushDown(o); if(lson[o]) PrintTree(lson[o]); s[++_tls]=os[o]; if(rson[o]) PrintTree(rson[o]); } int main() { srand(time(NULL));_seed=(unsigned)rand()*rand(); register int N=getnum<int>(),M=getnum<int>(); long long K=getnum<long long>(); int lq=0;getstr(os,lq); root=BuildTree(1,N); for(register int i=1;i<=M;i++) { register int l=getnum<int>(),r=getnum<int>(); //for(register int j=l;j<r-j+l;j++) // s[j]^=s[r-j+l]^=s[j]^=s[r-j+l]; int a,b,c,d; SplitTreeByOrder(root,r,a,b); SplitTreeByOrder(a,l-1,c,d); rev[d]^=1; root=MergeTree(c,MergeTree(d,b)); } PrintTree(root); for(register int i=26+1;i<=lq;i++) uf[i]=i; for(register int i=1;i<=N;i++) if(os[i] != s[i]) { if(os[i]>26 && s[i]>26) UnionMerge(s[i],os[i]); else qval[(os[i]>26 ? os[i] : s[i])]=(os[i]>26 ? s[i] : os[i]); } for(register int i=26+1;i<=lq;i++) if(qval[i]) qval[UnionFind(i)]=qval[i]; for(register int i=26+1;i<=lq;i++) if(!qval[i]) qval[i]=qval[UnionFind(i)]; static int lst[501010]; register int lf=0; for(register int i=26+1;i<=lq;i++) if(i == UnionFind(i) && !qval[i]) lst[++lf]=i; K--; for(register int i=lf;i>=1;i--) { qval[lst[i]]=K%26+1; K/=26; } for(register int i=26+1;i<=lq;i++) if(!qval[i]) qval[i]=qval[UnionFind(i)]; for(register int i=1;i<=N;i++) if(s[i] > 26) putchar('a'+qval[s[i]]-1); else putchar('a'+s[i]-1); putchar('\n'); return 0; } |