题目描述
长者在上网时,最喜欢看年轻人搞大新闻。
在一个新闻网页上,一开始有$n$条大新闻,每个新闻都有一个为正整数的$naive$值,按顺序有$m$个事件发生。
总共有$3$种事件:
$1.$最开始的大新闻被删除。
$2.$一个$naive$值为$x$的大新闻被添加到最前面。
$3.$长者询问从第$l$到第$r$个大新闻中$naive$值第$k$小的新闻的$naive$值。
作为所有记者中跑得最快的人,你要负责回答长者的询问,(当然不是为了$−1s$啊)。
输入格式
第一行为两个数$n,m$,意义如题所述。
接下来一行$n$个数,代表一开始$n$条大新闻的$naive$值。
接下来$m$行,每行一个操作,输入格式如下:
读入$1$,代表第一种事件。
读入$2,x$,代表第二种事件。
读入$3,l,r,k$,代表第三种事件。
输出格式
对于每一个第三种事件输出一行整数,代表答案
样例
样例输入:
6 8
2 7 4 3 5 9
3 2 5 3
1
2 4
3 1 4 2
2 6
3 1 7 5
1
3 3 6 4
样例输出:
5
4
6
9
数据范围与提示
样例解释:
初始序列为$2,7,4,3,5,9$。
询问$7,4,3,5$的第$3$小值,答案为$5$。
操作后序列变成$7,4,3,5,9$。
操作后序列变成$4,7,4,3,5,9$。
询问$4,7,4,3$的第$2$小值,答案为$4$。
操作后序列变成$6,4,7,4,3,5,9$。
询问序列$6,4,7,4,3,5,9$的第$5$小值,答案为$6$。
操作后序列变成$4,7,4,3,5,9$。
询问序列$4,3,5,9$的第$4$小值,答案为$9$。
数据范围:
对于$30\%$的数据,满足$1\leqslant n,m\leqslant 2,000$。
对于$50\%$的数据,满足$1\leqslant n,m\leqslant 30,000$。
对于$70\%$的数据,满足$1\leqslant n,m\leqslant 80,000$。
对于$100\%$的数据,满足$1\leqslant n,m\leqslant 2\times 10^5$。
保证数据合法,当没有新闻时不存在删除操作。
保证$1\leqslant naive$值$\leqslant 10^9$,保证$1\leqslant l\leqslant r\leqslant $当前新闻数,$k\leqslant r−l+1$。
题解
观察数据范围和操作,发现是主席树板子题(然而并不会打……)。
不会的先学一下主席树吧。
正解直接用的树上差分,少个$\log$。
时间复杂度:$(n+m)\log^2n$。
期望得分:$100$分。
实际得分:$100$分。
代码时刻
#include<bits/stdc++.h> using namespace std; int n,m; int a[200001],root[500000],tot; int trsum[10000001],lson[10000001],rson[10000001]; void insert(int &x,int pre,int l,int r,int w) { x=++tot; trsum[x]=trsum[pre]+1; lson[x]=lson[pre]; rson[x]=rson[pre]; if(l==r)return; int mid=(l+r)>>1; if(w<=mid)insert(lson[x],lson[pre],l,mid,w); else insert(rson[x],rson[pre],mid+1,r,w); } int ask(int x,int pre,int l,int r,int k) { if(l==r)return l; int mid=(l+r)>>1; if(trsum[lson[x]]-trsum[lson[pre]]>=k)return ask(lson[x],lson[pre],l,mid,k); else return ask(rson[x],rson[pre],mid+1,r,k-trsum[lson[x]]+trsum[lson[pre]]); } int main() { scanf("%d%d",&n,&m); for(int i=n;i;i--) scanf("%d",&a[i]); for(int i=1;i<=n;i++) insert(root[i],root[i-1],1,1<<30,a[i]); while(m--) { int opt; scanf("%d",&opt); switch(opt) { case 1:n--;break; case 2: int x; scanf("%d",&x); n++; insert(root[n],root[n-1],1,1<<30,x); break; case 3: int l,r,k; scanf("%d%d%d",&l,&r,&k); printf("%d\n",ask(root[n-l+1],root[n-r],1,1<<30,k)); break; } } return 0; }
rp++