Description

Input

從文件 pigeon.in 中讀入數據。
輸入第一行包含兩個正整數 n, m ，分別表示初始鴿籠數與操作個數。
第二行包含 n 個正整數，第 i 個數表示從左往右第 i 個初始鴿籠中鴿子的咕咕能力值 vi 。
接下去 m 行每行表示一個操作。操作輸入格式見題面描述。

Output

輸出到文件 pigeon.out 中。
輸出包含若干行，每行表示一個相應的 3 操作的答案。

Sample Input

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

Sample Output

5
4
6
9

Data Constraint

題目更正：vi值域小于等于1e9。

Solution

• 改修主席樹？？

• 其實不需要，我們只需要倒過來建靜態的主席樹即可，因為插入刪除都是在最左端。

• 為了節約一點點空間，我還打了個離散化。。

• 時間復雜度 $O(nlogn)$ 。

Code

#include<cstdio> #include<algorithm> #include<cctype> using namespace std; const int N=2e5+5; struct data {int v,l,r; }f[N*38],c[N]; struct number {int x,id; }a[N<<1]; int tot,num,qx,len; int rt[N<<1],rk[N<<1],pos[N]; inline int read() {int X=0,w=0; char ch=0;while(!isdigit(ch)) w|=ch=='-',ch=getchar();while(isdigit(ch)) X=(X<<3)+(X<<1)+(ch^48),ch=getchar();return w?-X:X; } void write(int x) {if(x>9) write(x/10);putchar(x%10+'0'); } inline bool cmp(number x,number y) {return x.x<y.x; } void make(int &v,int l,int r) {v=++tot;if(l==r) return;int mid=l+r>>1;make(f[v].l,l,mid);make(f[v].r,mid+1,r); } void insert(int &x,int pre,int l,int r) {f[x=++tot]=f[pre];f[x].v++;if(l==r) return;int mid=l+r>>1;if(qx<=mid) insert(f[x].l,f[pre].l,l,mid); else insert(f[x].r,f[pre].r,mid+1,r); } int find(int x,int pre,int l,int r,int k) {if(l==r) return a[l].x;int mid=l+r>>1,v=f[f[x].l].v-f[f[pre].l].v;if(v>=k) return find(f[x].l,f[pre].l,l,mid,k);return find(f[x].r,f[pre].r,mid+1,r,k-v); } int main() {freopen("pigeon.in","r",stdin);freopen("pigeon.out","w",stdout);int n=num=read(),m=read();for(int i=n;i;i--) a[a[i].id=i].x=read();for(int i=1;i<=m;i++){c[i].v=read()-2;if(!c[i].v){c[i].l=read();a[++num].x=c[i].l;a[num].id=num;pos[i]=num;}elseif(c[i].v>0) c[i].l=read(),c[i].r=read(),c[i].v=read();}sort(a+1,a+1+num,cmp);for(int i=1;i<=num;i++) rk[a[i].id]=i;make(rt[0],1,num);for(int i=1;i<=n;i++){len++;qx=rk[i];insert(rt[len],rt[len-1],1,num);}for(int i=1;i<=m;i++){if(c[i].v<0){rt[len--]=0;}elseif(!c[i].v){len++;qx=rk[pos[i]];insert(rt[len],rt[len-1],1,num);}else{int l=len-c[i].r+1,r=len-c[i].l+1,k=c[i].v;int ans=find(rt[r],rt[l-1],1,num,k);write(ans),putchar('\n');}}return 0; }

總結

以上是生活随笔為你收集整理的JZOJ 5933. 【NOIP2018模拟10.27】百鸽笼的全部內容，希望文章能夠幫你解決所遇到的問題。

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