CF 240F
做法：二维线段树，分别记录一个区间的小写字母个数，每次从小到大给两边分配（字典序最小）（区间更改）！
#include <bits/stdc++.h>
#define lson rt<<1,begin,mid
#define rson rt<<1|1,mid+1,end
using namespace std;
const int maxn= 100100;
char str[maxn];
int tree[maxn<<3][28];
int lazy[maxn<<3];
int book[28];
int n,m;
void cls(int rt)
{
lazy[rt]=-1;
for(int i=0;i<26;++i) tree[rt][i]=0;
}
void pushup(int rt)
{
for(int i=0;i<26;++i) tree[rt][i] = tree[rt<<1][i] + tree[rt<<1|1][i];
}
void pushdown(int rt,int begin,int end)
{
if(lazy[rt]!=-1)
{
int mid=(begin + end)/2;
int id=lazy[rt];
cls(rt<<1); cls(rt<<1|1);
tree[rt<<1][id]= (mid-begin+1);
tree[rt<<1|1][id] = (end-mid);
lazy[rt<<1]=lazy[rt<<1|1] =lazy[rt];
lazy[rt]=-1;
}
}
void build(int rt,int begin,int end)
{
cls(rt);
if(begin==end)
{
int id=str[begin] - 'a';
tree[rt][id]++;
lazy[rt]=id;
return;
}
int mid=(begin + end)>>1;
build(rson);
build(lson);
pushup(rt);
}
void updata(int rt,int begin,int end,int l,int r,int id)
{
if(begin>=l && r>=end)
{
cls(rt);
tree[rt][id] = (end-begin+1);
lazy[rt]=id;
return ;
}
pushdown(rt,begin,end);
int mid=(begin + end)>>1;
if(mid>=l) updata(lson,l,r,id);
if(r>mid) updata(rson,l,r,id);
pushup(rt);
}
void query(int rt,int begin,int end,int l,int r)
{
if(begin >=l && r>=end)
{
for(int i=0;i<26;++i) book[i]+=tree[rt][i];
return ;
}
pushdown(rt,begin,end);
int mid=(begin + end)>>1;
if(mid>=l) query(lson,l,r);
if(r>mid) query(rson,l,r);
pushup(rt);
}
void work(int l,int r)
{
memset(book,0,sizeof(book));
query(1,1,n,l,r);
int flag=0;
for(int i=0;i<26;++i)
{
if(book[i] % 2) flag++;
if(flag > 1) return;
}
int st=l,en=r;
int mid=l+(r-l+1)/2;
for(int i=0;i<26;++i)
{
if(book[i]==0) continue;
int temp= book[i]/2;
if(temp)
{
updata(1,1,n,st,st+temp-1,i);
updata(1,1,n,en-temp+1,en,i);
st= st+temp;
en= en-temp;
}
if(book[i]%2) updata(1,1,n,mid,mid,i);
}
}
int main()
{
freopen("input.txt","r",stdin);
freopen("output.txt","w",stdout);
scanf("%d%d",&n,&m);
scanf("%s",str+1);
build(1,1,n);
int a,b;
while(m--)
{
scanf("%d%d",&a,&b);
work(a,b);
}
for(int i=1;i<=n;++i)
{
memset(book,0,sizeof(book));
query(1,1,n,i,i);
for(int j=0;j<26;++j)
{
if(book[j])
{
putchar(j+'a');
break;
}
}
}
putchar(10);
return 0;
}
Cf 343D
做法：DFS序加线段树 ，这里要注意的是二操作，因为要区间修改其祖先很难实现。这时候我们可以这么想，先对修改点单点修改，然后在询问时，取DFS序子节点的min值即可。
注意：这里有一个wa点，如果当前点为0的话，在进行操作1的时候需要把这个0扔给它的祖先，避免在更改1后出现漏更改的情况！！！
#include <bits/stdc++.h>
#define lson rt<<1,begin,mid
#define rson rt<<1|1,mid+1,end
using namespace std;
const int maxn=500005;
int tree[maxn<<3];
int lazy[maxn<<3];
//如果其儿子有一点为0的话，那么本身也一定是0
void pushup(int rt)
{
tree[rt] = tree[rt<<1] && tree[rt<<1|1];
}
void pushdown(int rt)
{
if(lazy[rt]!=-1)
{
tree[rt<<1] = tree[rt<<1|1] =lazy[rt];
lazy[rt<<1|1] =lazy[rt<<1] =lazy[rt];
lazy[rt] = -1;
}
}
void updata(int rt,int begin,int end,int l,int r ,int x)
{
if(begin >= l && r>=end)
{
tree[rt] = x;
lazy[rt] = x;
return ;
}
pushdown(rt);
int mid=(begin + end)>>1;
if(mid >= l) updata(lson,l,r,x);
if(r>mid) updata(rson,l,r,x);
pushup(rt);
}
//单点更新
void updata2(int rt,int begin,int end,int pos)
{
if(begin==end)
{
tree[rt] = 0;
return ;
}
pushdown(rt);
int mid=(begin +end)>>1;
if(mid >=pos) updata2(lson,pos);
else updata2(rson,pos);
pushup(rt);
}
//儿子中如果有0的话，那么其点一定是0
int query(int rt,int begin, int end,int l,int r)
{
if(begin >=l && r>= end)
{
return tree[rt];
}
pushdown(rt);
int mid=(begin +end )>>1;
int a=3;
if(mid >=l) a= min( query(lson ,l,r),a);
if(r>mid) a=min(a, query(rson,l,r));
return a;
}
struct node
{
int to,next;
}edge[maxn<<1];
int head[maxn];
int cnt=0;
void add(int u,int v)
{
edge[cnt].to=v; edge[cnt].next=head[u]; head[u]=cnt++;
}
int fis[maxn];
int two[maxn];
int tot;
int fa[maxn];
void dfs(int u , int pre)
{
fis[u] = ++tot;
fa[u]=pre;
for(int i=head[u] ; i!=-1; i=edge[i].next )
{
int v=edge[i].to;
if(fis[v]==-1) dfs(v,u);
}
two[u]=tot;
}
int main()
{
int n;
while(scanf("%d",&n)!=EOF)
{
memset(head,-1,sizeof(head)); cnt=0;
for(int i=1;i<n;++i)
{
int a,b;
scanf("%d%d",&a,&b);
add(a,b); add(b,a);
}
memset(fis,-1,sizeof(fis)); tot=0;
dfs(1,-1);
memset(tree,0,sizeof(tree));
memset(lazy,-1,sizeof(lazy));
int m;
scanf("%d",&m);
while(m--)
{
int op,v;
scanf("%d%d",&op,&v);
if(op==1)
{
if(!query(1,1,tot,fis[v],two[v]) && fa[v]!=-1) updata2(1,1,tot,fis[fa[v]]);
// 如果其为0的话，那说明它的祖先也一定为0
updata(1,1,tot,fis[v],two[v],1);
}
else if(op==2)
{
updata2(1,1,tot,fis[v]);
//单点更新
}
else if(op==3)
{
printf("%d\n",query(1,1,tot,fis[v],two[v]));
}
}
}
return 0;
}
POJ 2104
做法：主席树模板（默默收藏一发）
#include <algorithm>
#include <iostream>
#include <cstdio>
#include <cstring>
using namespace std;
const int maxn= (100005<<2);
int tree[maxn*30],lson[maxn*30],rson[maxn*30];
int root[maxn],tot;
int a[maxn],myhash[maxn];
void build(int &rt,int begin ,int end)
{
rt = ++tot;
tree[rt]=0;
if(begin == end) return;
int mid=(begin+end)>>1;
build(lson[rt],begin,mid);
build(rson[rt],mid+1,end);
}
void updata(int pre,int &rt,int begin, int end,int pos)
{
rt = ++tot;
tree[rt] = tree[pre] +1;
lson[rt] = lson[pre];
rson[rt] = rson[pre];
if(begin == end) return;
int mid=(begin + end) >>1;
if(mid >= pos) updata(lson[pre],lson[rt],begin,mid,pos);
else updata(rson[pre],rson[rt],mid+1,end,pos);
}
int query(int pre,int rt,int begin ,int end,int k)
{
if(begin == end)
{
return begin;
}
int have = (tree[lson[rt]]-tree[lson[pre]]);
int mid = (begin+end)>>1;
if(have>=k) return query(lson[pre],lson[rt],begin,mid,k);
else return query(rson[pre],rson[rt],mid+1,end,k-have);
}
int main()
{
int n,m;
while(scanf("%d%d",&n,&m)!=EOF)
{
for(int i=1;i<=n;++i)
{
scanf("%d",&a[i]);
myhash[i]=a[i];
}
sort(myhash+1,myhash+n+1);
int cnt = unique(myhash+1,myhash+n+1) - myhash -1;
build(root[0], 1, cnt);
for(int i=1;i<=n;++i)
{
int temp = lower_bound(myhash+1,myhash+cnt+1,a[i]) - myhash;
updata(root[i-1],root[i],1,cnt,temp);
}
while(m--)
{
int l,r,k;
scanf("%d%d%d",&l,&r,&k);
printf("%d\n",myhash[query(root[l-1],root[r],1,cnt,k)]);
}
}
return 0;
}
