首页 > 代码库 > bzoj 4552: [Tjoi2016&Heoi2016]排序

bzoj 4552: [Tjoi2016&Heoi2016]排序

2024-09-12 23:50:11   220人阅读

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

5

HINT

 

 

思路

看过题解后，惊叹！

这题出的好，我给满分

它有个特性：是1~n的排列，局部排序只跟数的大小有关。

所以，有一个特别妙的方法：

二分答案mid,再检查第q位置上的数是>mid还是<=mid。

为了检查第q位置上的数经过m次操作后与mid的大小关系，

我们可以把原序列中>mid的数设为1，<=mid的数设为0。

这样，每次局部排序，就相当于对一个01数列进行排序，就能用线段树轻松地维护这个序列了。

最后查询第q位置上的数是1还是0即可。

非常妙啊

想不到设0、1的方法就已经滚出了/(ㄒoㄒ)/~~

 

代码

 1 #include <cstdio>
 2 #include <iostream>
 3 using namespace std;
 4 #define ref(i,x,y)for(int i=x;i<=y;++i)
 5 int read()
 6 {
 7     char c=getchar();int d=0,f=1;
 8     for(;c<‘0‘||c>‘9‘;c=getchar())if(c==‘-‘)f=-1;
 9     for(;c>=‘0‘&&c<=‘9‘;d=d*10+c-48,c=getchar());
10     return d*f;
11 }
12 const int N=100001;
13 int n,m,pos,s[N];
14 struct xint{int o,x,y;}q[N];
15 struct node{int x,y,s,tag;}a[N*10];
16 void pushdown(int t)
17 {
18     if(a[t].tag<0)return;
19     a[t<<1].tag=a[t].tag;
20     a[t<<1].s=(a[t<<1].y-a[t<<1].x+1)*a[t].tag;
21     a[t<<1|1].tag=a[t].tag;
22     a[t<<1|1].s=(a[t<<1|1].y-a[t<<1|1].x+1)*a[t].tag;
23     a[t].tag=-1;
24 }
25 void pushup(int t)
26 {
27     a[t].s=a[t<<1].s+a[t<<1|1].s;
28 }
29 void build(int x,int y,int t)
30 {
31     a[t].tag=-1;
32     a[t].x=x;a[t].y=y;
33     if(x==y)return;
34     int m=(x+y)>>1;
35     build(x,m,t<<1);
36     build(m+1,y,t<<1|1);
37 }
38 void modify(int x,int y,int t,int s)
39 {
40     if(x<=a[t].x&&a[t].y<=y)
41     {
42         a[t].tag=s;
43         a[t].s=(a[t].y-a[t].x+1)*s;
44         return;
45     }
46     pushdown(t);
47     int m=(a[t].x+a[t].y)>>1;
48     if(x<=m)modify(x,y,t<<1,s);
49     if(m<y)modify(x,y,t<<1|1,s);
50     pushup(t);
51 }
52 int query(int x,int y,int t)
53 {
54     if(x<=a[t].x&&a[t].y<=y)return a[t].s;
55     pushdown(t);
56     int m=(a[t].x+a[t].y)>>1,res=0;
57     if(x<=m)res+=query(x,y,t<<1);
58     if(m<y)res+=query(x,y,t<<1|1);
59     return res;
60 }
61 int check(int x)
62 {
63     ref(i,1,n)modify(i,i,1,s[i]>x);
64     ref(i,1,m)
65     {
66         int s=query(q[i].x,q[i].y,1);
67         if(q[i].o==0)
68         {
69             if(q[i].y-s>=q[i].x)
70                 modify(q[i].x,q[i].y-s,1,0);
71             if(s)modify(q[i].y-s+1,q[i].y,1,1);
72         }
73         if(q[i].o==1)
74         {
75             if(s)modify(q[i].x,q[i].x+s-1,1,1);
76             if(q[i].y>=q[i].x+s)
77                 modify(q[i].x+s,q[i].y,1,0);
78         }
79     }
80     return query(pos,pos,1);
81 }
82 int main()
83 {
84     n=read(),m=read();
85     ref(i,1,n)s[i]=read();
86     ref(i,1,m)q[i].o=read(),q[i].x=read(),q[i].y=read();
87     pos=read();
88     build(1,n,1);
89     int l=1,r=n;
90     while(l<r)
91     {
92         int m=(l+r)>>1;
93         if(check(m))l=m+1;else r=m;
94     }
95     cout<<l<<endl;
96 }

 

bzoj 4552: [Tjoi2016&Heoi2016]排序


联系
我们