本文共 1460 字，大约阅读时间需要 4 分钟。
大意: 给定字符串, 每次删除一段区间的某种字符, 最后输出序列.
类似于splay维护序列. 每次删除都会影响到后面字符的位置
可以通过转化为查询前缀和=k来查找下标.
#include #include #include #include #include #include #include #include #include #include #include #define REP(i,a,n) for(int i=a;i<=n;++i)#define PER(i,a,n) for(int i=n;i>=a;--i)#define hr putchar(10)#define pb push_back#define lc (o<<1)#define rc (lc|1)#define mid ((l+r)>>1)#define ls lc,l,mid#define rs rc,mid+1,rusing namespace std;const int N = 2e5+10;int n, m;char s[N];int tr[63][N<<2];bool vis[63][N<<2];inline void pu(int o) { REP(i,1,62) tr[i][o]=tr[i][lc]+tr[i][rc];}inline void pd(int o) { REP(i,1,62) if (vis[i][o]) { tr[i][lc]=0,vis[i][lc]=1; tr[i][rc]=0,vis[i][rc]=1; vis[i][0]=0; }}int get(char x) { if ('0'<=x&&x<='9') return x-'0'+1; if ('A'<=x&&x<='Z') return x-'A'+11; return x-'a'+37;}void build(int o, int l, int r) { if (l==r) ++tr[get(s[l])][o]; else build(ls),build(rs),pu(o);}int find(int o, int l, int r, int k) { if (l==r) return l; int s = 0; REP(i,1,62) { if (vis[i][o]) { tr[i][lc]=0,vis[i][lc]=1; tr[i][rc]=0,vis[i][rc]=1; vis[i][o]=0; } else s+=tr[i][lc]; } if (s>=k) return find(ls,k); return find(rs,k-s);}void update(int o, int l, int r, int ql, int qr, int v) { if (ql<=l&&r<=qr) return tr[v][o]=0,vis[v][o]=1,void(); pd(o); if (mid>=ql) update(ls,ql,qr,v); if (mid
转载于:https://www.cnblogs.com/uid001/p/10764701.html