題目鏈接：http://61.187.179.132/JudgeOnline/problem.php?id=1901

題意：給出一個數列，兩種操作：（1）詢問區間第K小值；（2）修改某個位置的值。

思路：首先，將數列建成線段樹。線段樹的每個節點建立一棵treap，以方便統計。插入時，從上到下，刪除原位置上的數字的值，插入新的值；詢問時，二分答案x，在區間查找小于等于x的個數與K比較。

?

struct Node
{
? ? int val,size,pri;
? ? int L,R;
};




Node a[N*100];
int e;


struct node
{
? ? int L,R,root;
};


node A[N<<2];


int d[N];


int newNode(int val)
{
? ? int x=++e;
? ? a[x].val=val;
? ? a[x].size=1;
? ? a[x].L=a[x].R=-1;
? ? a[x].pri=rand();
? ? return x;
}


void pushUp(int k)
{
? ? if(k==-1) return;
? ? a[k].size=1;
? ? if(a[k].L!=-1) a[k].size+=a[a[k].L].size;
? ? if(a[k].R!=-1) a[k].size+=a[a[k].R].size;
}


void rotL(int &x)
{
? ? int y=a[x].R;
? ? a[x].R=a[y].L;
? ? a[y].L=x;
? ??
? ? pushUp(x);
? ? pushUp(y);
? ? x=y;
}


void rotR(int &x)
{
? ? int y=a[x].L;
? ? a[x].L=a[y].R;
? ? a[y].R=x;
? ??
? ? pushUp(x);
? ? pushUp(y);
? ? x=y;
}






void insert(int &k,int val)
{
? ? if(k==-1)
? ? {
? ? ? ? k=newNode(val);
? ? }
? ? else if(val<a[k].val)
? ? {
? ? ? ? insert(a[k].L,val);
? ? ? ? if(a[a[k].L].pri>a[k].pri) rotR(k);
? ? }
? ? else
? ? {
? ? ? ? insert(a[k].R,val);
? ? ? ? if(a[a[k].R].pri>a[k].pri) rotL(k);
? ? }
? ? pushUp(k);
}




void del(int val,int &k)
{
? ? if(k==-1) return;
? ? else if(val<a[k].val)?
? ? {
? ? ? ? del(val,a[k].L);
? ? }
? ? else if(val>a[k].val)?
? ? {
? ? ? ? del(val,a[k].R);
? ? }
? ? else
? ? {
? ? ? ? if(a[k].L==-1&&a[k].R==-1) k=-1;
? ? ? ? else if(a[k].L==-1)?
? ? ? ? {
? ? ? ? ? ? k=a[k].R;
? ? ? ? }
? ? ? ? else if(a[k].R==-1)?
? ? ? ? {
? ? ? ? ? ? k=a[k].L;
? ? ? ? }
? ? ? ? else?
? ? ? ? {
? ? ? ? ? ? if(a[a[k].L].pri<a[a[k].R].pri)
? ? ? ? ? ? {
? ? ? ? ? ? ? ? rotL(k);
? ? ? ? ? ? ? ? del(val,a[k].L);
? ? ? ? ? ? }
? ? ? ? ? ? else
? ? ? ? ? ? {
? ? ? ? ? ? ? ? rotR(k);
? ? ? ? ? ? ? ? del(val,a[k].R);
? ? ? ? ? ? }
? ? ? ? }
? ? }
? ? pushUp(k);
}


int cal(int k,int root)
{
? ? int ans=0,p=root;
? ? while(p!=-1)
? ? {
? ? ? ? if(k<a[p].val) p=a[p].L;
? ? ? ? else?
? ? ? ? {
? ? ? ? ? ? ans++;
? ? ? ? ? ? if(a[p].L!=-1) ans+=a[a[p].L].size;
? ? ? ? ? ? p=a[p].R;
? ? ? ? }
? ? }
? ? return ans;
}


void build(int t,int L,int R)
{
? ? A[t].L=L;
? ? A[t].R=R;
? ??
? ? A[t].root=newNode(d[L]);
? ? int i;
? ? for(i=L+1;i<=R;i++)?
? ? {
? ? ? ? insert(A[t].root,d[i]);
? ? }
? ??
? ? if(L==R) return;
? ? int mid=(L+R)>>1;
? ? build(t*2,L,mid);
? ? build(t*2+1,mid+1,R);
}


int DFS(int t,int L,int R,int k)
{
? ? if(L>A[t].R||R<A[t].L) return 0;
? ? if(L<=A[t].L&&A[t].R<=R)
? ? {
? ? ? ? return cal(k,A[t].root);
? ? }
? ? return DFS(t*2,L,R,k)+DFS(t*2+1,L,R,k);
}


int query(int L,int R,int k)
{
? ? int low=-5,high=INF,mid,ans;
? ? while(low<=high)
? ? {
? ? ? ? mid=(low+high)>>1;
? ? ? ? if(DFS(1,L,R,mid)>=k) ans=mid,high=mid-1;
? ? ? ? else low=mid+1;
? ? }
? ? return ans;
}


int n,m;


void update(int t,int pos,int k)
{
? ? if(pos<A[t].L||pos>A[t].R) return;
? ? del(d[pos],A[t].root);
? ? insert(A[t].root,k);
? ? update(t*2,pos,k);
? ? update(t*2+1,pos,k);
}


int main()
{
? ? RD(n,m);
? ? int i;
? ? FOR1(i,n) RD(d[i]);
? ? build(1,1,n);
? ? int L,R,k;
? ? char op[5];
? ? while(m--)
? ? {
? ? ? ? RD(op);
? ? ? ? if(op[0]=='Q')
? ? ? ? {
? ? ? ? ? ? RD(L,R,k);
? ? ? ? ? ? if(L>R) swap(L,R);
? ? ? ? ? ? PR(query(L,R,k));
? ? ? ? }
? ? ? ? else
? ? ? ? {
? ? ? ? ? ? RD(L,R);
? ? ? ? ? ? update(1,L,R);
? ? ? ? ? ? d[L]=R;
? ? ? ? }
? ? }
}

總結

以上是生活随笔為你收集整理的BZOJ 1901 Dynamic Rankings（线段树+treap）的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。