| WZJ的数据结构（负十四） |
| 难度级别：D； 运行时间限制：6000ms； 运行空间限制：262144KB； 代码长度限制：2000000B |
|
试题描述
|
|
请你设计一个数据结构，完成以下功能： 给定一个大小为N的整数组A，M次操作，操作分两种： 1.1 i j k 每次询问给你i,j,k三个参数，求Ai至Aj中第k小的数。 2.0 x v 每次操作给你x,v两个参数，将A[x]改成v。 |
|
输入
|
|
第一行为两个正整数N，M。
第二行为N个正整数Ai。 接下来M行为操作。 |
|
输出
|
|
对于每个询问输出答案（保证k合法）。
|
|
输入示例
|
|
6 8
1 3 2 2 5 3 1 1 3 2 1 1 4 2 1 1 4 3 1 1 4 4 0 4 3 1 1 4 3 0 2 5 1 1 4 4 |
|
输出示例
|
|
2
2 2 3 3 5 |
|
其他说明
|
|
1<=N,M,Ai,v<=100000
1<=i<=j<=N 1<=k<=j-i+1 1<=x<=N |
写一个二分+树状数组+Treap，挺爽的
#include<cstdio>
#include<cctype>
#include<queue>
#include<ctime>
#include<cstring>
#include<algorithm>
#define rep(s,t) for(int i=s;i<=t;i++)
#define ren for(int i=first[x];i!=-1;i=next[i])
using namespace std;
inline int read() {
int x=,f=;char c=getchar();
for(;!isdigit(c);c=getchar()) if(c=='-') f=-;
for(;isdigit(c);c=getchar()) x=x*+c-'';
return x*f;
}
const int maxn=;
const int maxnode=;
struct Node {
Node* ch[];
int r,s,v;
void maintain() {s=ch[]->s+ch[]->s+;}
}nodes[maxnode],*null=&nodes[];
queue<Node*> del;
int n,A[maxn],ToT;
Node* newnode(int v) {
Node* o;
if(!del.empty()) o=del.front(),del.pop();
else o=&nodes[++ToT];
o->ch[]=o->ch[]=null;
o->s=;o->v=v;o->r=rand();
return o;
}
void remove(Node* &o) {
del.push(o);o=null;
}
void rotate(Node* &o,int d) {
Node* k=o->ch[d^];o->ch[d^]=k->ch[d];k->ch[d]=o;
o->maintain();k->maintain();o=k;
}
void insert(Node* &o,int v) {
if(o==null) o=newnode(v);
else {
int d=v>o->v;insert(o->ch[d],v);
if(o->ch[d]->r>o->r) rotate(o,d^);
else o->maintain();
}
}
void remove(Node* &o,int v) {
if(o->v==v) {
Node* t=o;
if(o->ch[]==null) o=o->ch[],remove(t);
else if(o->ch[]==null) o=o->ch[],remove(t);
else {
int d=o->ch[]->r>o->ch[]->r;
rotate(o,d);remove(o->ch[d],v);
}
}
else remove(o->ch[v>o->v],v);
if(o!=null) o->maintain();
}
void print(Node* o) {
if(o==null) return;
print(o->ch[]);
printf("%d ",o->v);
print(o->ch[]);
}
int query(Node* &o,int v) {
if(o==null) return ;
if(v<=o->v) return query(o->ch[],v);
return query(o->ch[],v)+o->ch[]->s+;
}
Node* root[maxn];
void insert(int x,int v) {for(;x<=n;x+=x&-x) insert(root[x],v);}
void update(int x,int v) {for(;x<=n;x+=x&-x) remove(root[x],v);}
int query(int x,int v) {int ret=;for(;x;x-=x&-x) ret+=query(root[x],v+);return ret;}
int main() {
null->s=;srand(time());
n=read();int m=read();
rep(,n) root[i]=null;
rep(,n) insert(i,A[i]=read());
while(m--) {
if(read()) {
int l=read(),r=read(),k=read();
int L=,R=,M;
while(L<R) if(query(r,M=L+R>>)-query(l-,M=L+R>>)>=k) R=M; else L=M+;
printf("%d\n",L);
}
else {
int x=read();update(x,A[x]);
insert(x,A[x]=read());
}
}
return ;
}
复习一下树状数组+可持久化线段树，写WA了一发真不爽
#include<cstdio>
#include<cctype>
#include<queue>
#include<cstring>
#include<algorithm>
#define rep(s,t) for(int i=s;i<=t;i++)
#define ren for(int i=first[x];i!=-1;i=next[i])
using namespace std;
inline int read() {
int x=,f=;char c=getchar();
for(;!isdigit(c);c=getchar()) if(c=='-') f=-;
for(;isdigit(c);c=getchar()) x=x*+c-'';
return x*f;
}
const int maxn=;
const int maxnode=;
int ls[maxnode],rs[maxnode],s[maxnode],ToT;
int n,m,A[maxn],root[maxn],c[maxn];
void update(int& y,int x,int l,int r,int pos,int v) {
s[y=++ToT]=s[x]+v;if(l==r) return;
int mid=l+r>>;ls[y]=ls[x];rs[y]=rs[x];
if(pos<=mid) update(ls[y],ls[x],l,mid,pos,v);
else update(rs[y],rs[x],mid+,r,pos,v);
}
void update(int x,int v) {
for(int i=x;i<=n;i+=i&-i) update(c[i],c[i],,,A[x],-);
for(int i=x;i<=n;i+=i&-i) update(c[i],c[i],,,A[x]=v,);
}
int lt[maxn],rt[maxn],ltot,rtot;
void get(int x,int tp) {
if(!tp) {lt[ltot=]=root[x];for(;x;x-=x&-x) if(c[x]) lt[++ltot]=c[x];}
else {rt[rtot=]=root[x];for(;x;x-=x&-x) if(c[x]) rt[++rtot]=c[x];}
}
int main() {
n=read();m=read();
rep(,n) update(root[i],root[i-],,,A[i]=read(),);
while(m--) {
if(!read()) {
int x=read(),v=read();
update(x,v);
}
else {
int ql=read(),qr=read(),k=read();
get(ql-,);get(qr,);int l=,r=;
while(l<r) {
int mid=l+r>>,tot=;
rep(,ltot) tot-=s[ls[lt[i]]];
rep(,rtot) tot+=s[ls[rt[i]]];
if(tot>=k) {
r=mid;
rep(,ltot) lt[i]=ls[lt[i]];
rep(,rtot) rt[i]=ls[rt[i]];
}
else {
l=mid+;k-=tot;
rep(,ltot) lt[i]=rs[lt[i]];
rep(,rtot) rt[i]=rs[rt[i]];
}
}
printf("%d\n",l);
}
}
return ;
}