[BZOJ4552]排序-布布扣-bubuko.com

Description

在2016年，佳媛姐姐喜欢上了数字序列。因而他经常研究关于序列的一些奇奇怪怪的问题，现在他在研究一个难题

，需要你来帮助他。这个难题是这样子的：给出一个1到n的全排列，现在对这个全排列序列进行m次局部排序，排

序分为两种：1:(0,l,r)表示将区间[l,r]的数字升序排序2:(1,l,r)表示将区间[l,r]的数字降序排序最后询问第q

位置上的数字。

Input

输入数据的第一行为两个整数n和m。n表示序列的长度，m表示局部排序的次数。1 <= n, m <= 10^5第二行为n个整

数，表示1到n的一个全排列。接下来输入m行，每一行有三个整数op, l, r, op为0代表升序排序，op为1代表降序

排序, l, r 表示排序的区间。最后输入一个整数q，q表示排序完之后询问的位置, 1 <= q <= n。1 <= n <= 10^5

，1 <= m <= 10^5

Output

输出数据仅有一行，一个整数，表示按照顺序将全部的部分排序结束后第q位置上的数字。

Sample Input

6 3
1 6 2 5 3 4
0 1 4
1 3 6
0 2 4
3

Sample Output

二分答案后转化为01序列，用线段树维护，算是很常见的套路了

代码：

 1 #include<iostream>
 2 #include<cstdio>
 3 #include<algorithm>
 4 #define M 100010
 5 #define ls node<<1
 6 #define rs node<<1|1
 7 using namespace std;
 8 int n,m,ans,l,r,k;
 9 int a[M],b[M],opt[M],L[M],R[M],val[M<<2],tag[M<<2];
10 
11 void update(int node) {val[node]=val[ls]+val[rs];}
12 
13 void push(int node,int l,int r)
14 {
15     if(tag[node]!=-1)
16     {
17         int mid=(l+r)/2,v=tag[node];
18         val[ls]=v*(mid-l+1);
19         val[rs]=v*(r-mid);
20         tag[ls]=tag[rs]=v;
21         tag[node]=-1;
22     }
23 }
24 
25 void build(int node,int l,int r)
26 {
27     tag[node]=-1;
28     if(l==r) {val[node]=b[l];return;}
29     int mid=(l+r)/2;
30     build(ls,l,mid); build(rs,mid+1,r);
31     update(node);
32 }
33 
34 void change(int node,int l,int r,int l1,int r1,int v)
35 {
36     if(l1<=l&&r1>=r)
37     {
38         tag[node]=v;
39         val[node]=(r-l+1)*v;
40         return;
41     }
42     if(l1>r||r1<l) return;
43     int mid=(l+r)/2; push(node,l,r);
44     change(ls,l,mid,l1,r1,v); change(rs,mid+1,r,l1,r1,v);
45     update(node);
46 }
47 
48 int query(int node,int l,int r,int l1,int r1)
49 {
50     if(l1<=l&&r1>=r) return val[node];
51     if(l1>r||r1<l) return 0;
52     int mid=(l+r)/2; push(node,l,r);
53     return query(ls,l,mid,l1,r1)+query(rs,mid+1,r,l1,r1);
54 }
55 
56 bool check(int mid)
57 {
58     for(int i=1;i<=n;i++)
59         b[i]=a[i]>=mid?1:0;
60     build(1,1,n);
61     for(int i=1;i<=m;i++)
62     {
63         if(opt[i]==0) 
64         {
65             int num=query(1,1,n,L[i],R[i]);
66             change(1,1,n,R[i]-num+1,R[i],1);
67             change(1,1,n,L[i],R[i]-num,0);
68         }
69         else
70         {
71             int num=query(1,1,n,L[i],R[i]);
72             change(1,1,n,L[i],L[i]+num-1,1);
73             change(1,1,n,L[i]+num,R[i],0);
74         }
75     }
76     return query(1,1,n,k,k);
77 }
78 
79 int main()
80 {
81     scanf("%d%d",&n,&m);
82     for(int i=1;i<=n;i++) scanf("%d",&a[i]);
83     for(int i=1;i<=m;i++) scanf("%d%d%d",&opt[i],&L[i],&R[i]);
84     scanf("%d",&k);l=1,r=n;
85     while(l<=r)
86     {
87         int mid=(l+r)/2;
88         if(check(mid)) l=mid+1,ans=mid;
89         else r=mid-1;
90     }
91     printf("%d",ans);
92     return 0;
93 }

[BZOJ4552]排序

原文：https://www.cnblogs.com/Slrslr/p/9748956.html