#精准剖析<大新闻>

1 1. 最开始的大新闻被删除
2 2. 一个 naive 值为 x 的大新闻被添加到最前面
3 3. 长者询问从第 l 到第 r 个大新闻中 naive 值第 k 小的新闻的 naive 值

describe

看到区间的第k小值，是主席树。但1，2的修改操作有点chi_shi，仔细分析。发现1，2两个修改的范围有点蹊跷啊，都是在序列开头动手的，而我们正常的主席树第一棵树是不能丢的啊（因为所有节点都有第一棵树的信息）。正难则反（%A部男神Yang_guangjie），我们可以倒着建树，那么所有修改都变成作用在序列最后。

那么删点直接清空

加点直接动态开点，合并

询问注意对应区间的l，r

 1 #include<bits/stdc++.h>
 2 #define MAXN 200010 
 3 #define RR 1000000000
 4 using namespace std;
 5 int n,m;
 6 int rn[MAXN];
 7 int root[MAXN*100],ls[MAXN*100],rs[MAXN*100],num;
 8 int gs;
 9 int sm[MAXN*100];
10 void insert(int &u,int l,int r,int val){
11     if(!u)u=++num;
12     if(l==r){++sm[u];return ; }
13     int mid=l+r>>1;
14     if(val<=mid)insert(ls[u],l,mid,val);
15     else insert(rs[u],mid+1,r,val);
16     sm[u]=sm[ls[u]]+sm[rs[u]];
17 }
18 int mergeTREE(int x,int y){
19     if(!x||!y)return x+y;
20     ls[x]=mergeTREE(ls[x],ls[y]);
21     rs[x]=mergeTREE(rs[x],rs[y]);
22     sm[x]=sm[x]+sm[y];//accepted
23     return x;
24 }
25 int query(int d1,int d2,int l,int r,int k){
26     if(l==r)return l;
27     int tt=sm[ls[d2]]-sm[ls[d1]];
28     int mid=l+r>>1;
29     if(k<=tt)return query(ls[d1],ls[d2],l,mid,k);
30     else return query(rs[d1],rs[d2],mid+1,r,k-tt);
31 }
32 int main(){
33     scanf("%d%d",&n,&m);
34     gs=n;
35     for(int i=n;i>=1;--i)scanf("%d",&rn[i]);
36     for(int i=1;i<=n;++i){
37         insert(root[i],1,RR,rn[i]);
38         root[i]=mergeTREE(root[i],root[i-1]);
39     }
40     int opt,x,l,r,k;
41     while(m--){
42         scanf("%d",&opt);
43         if(opt==1)root[gs]=ls[root[gs]]=rs[root[gs]]=sm[root[gs]]=0,--gs;
44         else if(opt==2){
45             scanf("%d",&x);++gs;
46             insert(root[gs],1,RR,x);
47             root[gs]=mergeTREE(root[gs],root[gs-1]);
48         }
49         else{
50             scanf("%d%d%d",&l,&r,&k);
51             printf("%d
",query(root[gs-r],root[gs-l+1],1,RR,k));
52         }
53     }
54 }

View Code

仔细申题，深度剖析