题目传送门（内部题60）
输入格式
第一行三个数$n,m,k$。
第二行一个长度为$n$的串。
接下来$m$行每行两个数$L_i$和$R_i$。
输出格式
一个串，表示字典序第$k$小的合法的能被填出的串。
样例
样例输入：
12 1 4
ztrs?a?isred
5 7
样例输出：
ztrsdadisred
数据范围与提示
对于$10\%$的数据，保证$n,m\leqslant 100$。
对于$30\%$的数据，保证$n,m\leqslant 5,000$。
对于另外$10\%$的数据（包含于$70\%$的数据），保证$n\leqslant 5,000$。
对于另外$10\%$的数据（包含于$70\%$的数据），保证$m\leqslant 5,000$。
对于$70\%$的数据，保证$n,m\leqslant 5\times {10}^4$。
对于另外$10\%$的数据，保证$k\leqslant 100$。
对于$100\%$的数据，保证$n,m\leqslant 5\times {10}^5,k\leqslant 1\times {10}^{18}$。
题解
先不考虑区间反转的复杂度问题，只考虑翻转之后如何统计答案。
这时候会出现有些位必须是一样的，这时候如果其中有一位是字符，那么这些位必须都是一个字符；当然不会出现两种不同的字符，因为这样就无解了。
接着考虑第$k$小的问题，显然我们只能从有些位是一样的并且其中没有字符的做手脚，因为它们是可以随便赋值的，而字符串的字典序的大小取决于它们中位置最靠前的；那么现在假设有$p$个位置可以随意赋成不一样的值，那么我们也就是将$k$转化成$26$进制，然后从后往前，从低位往高位给串赋值，剩下的都赋成$a$即可。
这道题出题人卡了$rope$的常，导致无旋$Treap$和单旋$Splay$都也被卡了；然而我打的就是$Splay$，所以我卡了好长时间的常；第一个$A$掉这道题的也说是评测机哆嗦了一下，再交一遍就不行了。那么我下面讲一下我的卡常心得，部分有关卡常代码在下方“代码时刻”中给出。
$\alpha.register$显然必不可少。
$\beta.$快读$+fread$。$fread\downarrow$
const int L=1<<20|1;
char buffer[L],*S,*T;
#define getchar() ((S==T&&(T=(S=buffer)+fread(buffer,1,L,stdin),S==T))?EOF:*S++)
$\gamma.$老师不让用全局$O3$，于是我可以在代码中手开了部分$O3$。对于函数的$O3\downarrow$
#define inline __attribute__((optimize("-O3")))
$\delta.bool$和部分值域较小变量换成$char$，这将让你的代码跑的飞快。
$\epsilon.$局部变量不要开全局。
$\zeta.$另外对于$HZOI$的小朋友们，可以使用连续提交的策略，让评测机预热一下，一般情况下五遍以内就过了。
有了这些卡常工具，你就可以轻松$AC$此题了。
下面给出我在这道题的卡常历程，一共$38$次$TLE\downarrow$
不过结局总是好的$downarrow$
时间复杂度：$\Theta(n\log n)$。
期望得分：$100$分。
实际得分：$80\sim 100$分（看你怎么卡常了）。
代码时刻
#include<bits/stdc++.h>
using namespace std;
const int L=1<<20|1;
char buffer[L],*S,*T;
#define inline __attribute__((optimize("-O3")))
#define getchar() ((S==T&&(T=(S=buffer)+fread(buffer,1,L,stdin),S==T))?EOF:*S++)
inline int Read(){
register int ret;
register char r;
while(r=getchar(),r<'0'||r>'9');ret=r-48;
while(r=getchar(),r>='0'&&r<='9')ret=(ret<<3)+(ret<<1)+r-48;
return ret;
}
int n,m;
long long K,bas[15];
char ch[500005],ans[500005];
int trfat[500005],trson[500005][2],trsiz[500005];
char trlaz[500005];
int root;
int b[500005],bel[500005],block,st[500005];
char vis[500005];
inline void pushup(register int x){trsiz[x]=trsiz[trson[x][0]]+trsiz[trson[x][1]]+1;}
inline void pushdown(register int x)
{
if(x&&trlaz[x])
{
trlaz[trson[x][0]]^=1;
trlaz[trson[x][1]]^=1;
swap(trson[x][0],trson[x][1]);
trlaz[x]=0;
}
}
inline void build(register int father,register int l,register int r)
{
if(l>r)return;
register int mid=(l+r)>>1;
trfat[mid]=father;
mid>father?trson[father][1]=mid:trson[father][0]=mid;
build(mid,l,mid-1);
build(mid,mid+1,r);
pushup(mid);
}
inline void rotate(register int x)
{
register int father=trfat[x];
register int grandf=trfat[father];
register char myself=trson[trfat[x]][1]==x;
pushdown(father);
pushdown(x);
if(grandf)trson[grandf][trson[trfat[father]][1]==father]=x;
trson[father][myself]=trson[x][myself^1];
trfat[trson[father][myself]]=father;
trson[x][myself^1]=father;
trfat[father]=x;
trfat[x]=grandf;
pushup(father);
pushup(x);
}
inline void splay(register int x,register int k)
{
for(register int father;(father=trfat[x])!=k;rotate(x))
if(trfat[father]!=k)rotate((trson[trfat[x]][1]==x)==(trson[trfat[father]][1]==father)?father:x);
if(!k)root=x;
}
inline int rank(register int x)
{
register int now=root;
while(1)
{
pushdown(now);
if(x<=trsiz[trson[now][0]])now=trson[now][0];
else
{
x-=trsiz[trson[now][0]]+1;
if(!x)return now;
now=trson[now][1];
}
}
}
inline void turn(register int l,register int r)
{
l=rank(l);
r=rank(r+2);
splay(l,0);
splay(r,l);
pushdown(root);
trlaz[trson[trson[root][1]][0]]^=1;
}
inline int get_pow(register long long x)
{
register int lft=0,rht=14,res=0;
while(lft<=rht)
{
int mid=(lft+rht)>>1;
bas[mid]<=x?lft=mid+1,res=mid:rht=mid-1;
}
return res;
}
inline void work()
{
scanf("%d%d%lld",&n,&m,&K);
scanf("%s",ch+1);
K--;bas[0]=1;
for(register int i=1;i<15;i++)bas[i]=bas[i-1]*26;
build(0,1,n+2);root=(n+3)>>1;
while(m--)
{
register int l=Read(),r=Read();
turn(l,r);
}
for(register int i=1;i<=n;i++)
b[i]=rank(i+1)-1;
for(register int i=1;i<=n;i++)
if(!bel[i])
{
block++;
int x=i;
while(!bel[x])
{
bel[x]=block;
x=b[x];
}
}
register int top=0;
for(register int i=1;i<=n;i++)
if(ch[i]!='?')ans[bel[i]]=ch[i];
for(register int i=1;i<=n;i++)
if(!ans[bel[i]]&&!vis[bel[i]])
{
vis[bel[i]]=1;
st[++top]=bel[i];
}
while(K)
{
register int x=get_pow(K);
ans[st[top-x]]='a'+K/bas[x];
K-=bas[x]*(K/bas[x]);
}
for(register int i=1;i<=top;i++)
if(!ans[st[i]])ans[st[i]]='a';
for(register int i=1;i<=n;i++)
putchar(ans[bel[i]]);
}
int main()
{
work();
return 0;
}
rp++