题目
Problem Description
DZY has a sequence a[1..n]. It is a permutation of integers 1∼n.
Now he wants to perform two types of operations:
0lr: Sort a[l..r] in increasing order.
1lr: Sort a[l..r] in decreasing order.
After doing all the operations, he will tell you a position k, and ask you the value of a[k].
Input
First line contains t, denoting the number of testcases.
t testcases follow. For each testcase:
First line contains n,m. m is the number of operations.
Second line contains n space-separated integers a[1],a[2],⋯,a[n], the initial sequence. We ensure that it is a permutation of 1∼n.
Then m lines follow. In each line there are three integers opt,l,r to indicate an operation.
Last line contains k.
(1≤t≤50,1≤n,m≤100000,1≤k≤n,1≤l≤r≤n,opt∈{0,1}. Sum of n in all testcases does not exceed 150000. Sum of m in all testcases does not exceed 150000)
Output
For each testcase, output one line - the value of a[k] after performing all m operations.
Sample Input
1
6 3
1 6 2 5 3 4
0 1 4
1 3 6
0 2 4
3
Sample Output
5
思路
题目比较特殊，由于数字是全排列，而且询问只有一次，所以我们选择二分答案，并且把大于等于mid置为1，小于置为0,然后用线段树去进行区间修改，最后询问k点是否为1，进行二分。
代码实现
#include<cstdio>
#include<algorithm>
#include<vector>
#include<queue>
#include<map>
#include<iostream>
#include<cstring>
#include<cmath>
using namespace std;
#define rep(i,f_start,f_end) for (int i=f_start;i<=f_end;++i)
#define per(i,n,a) for (int i=n;i>=a;i--)
#define MT(x,i) memset(x,i,sizeof(x) )
#define rev(i,start,end) for (int i=start;i<end;i++)
#define inf 0x3f3f3f3f
#define mp(x,y) make_pair(x,y)
#define lowbit(x) (x&-x)
#define MOD 1000000007
#define exp 1e-8
#define N 1000005
#define fi first
#define se second
#define pb push_back
typedef long long ll;
typedef pair<int ,int> PII;
typedef pair<int ,PII> PIII;
ll gcd (ll a,ll b) {return b?gcd (b,a%b):a; }
const int maxn=1e5+7;
int op[maxn],qr[maxn],ql[maxn],k,a[maxn];
int n,m;
struct node {
int l,r;
int data,add;
void update (int val) {
data= (r-l+1)*val;
add=val;
}
}tree[maxn*4];
inline void buildtree (int k,int l,int r) {
tree[k].l=l,tree[k].r=r;
tree[k].data=0;
tree[k].add=-1;
if (l==r) return ;
int mid= (l+r)>>1;
buildtree (k*2,l,mid);
buildtree (k*2+1,mid+1,r);
}
inline void lazydown (int k) {
if (tree[k].add!=-1) {
tree[k*2].update (tree[k].add),tree[k*2+1].update (tree[k].add);
tree[k].add=-1;
}
}
inline void update (int k,int l,int r,int val) {
if (l<=tree[k].l&&r>=tree[k].r) {
tree[k].update (val);
return ;
}
lazydown (k);
int mid= (tree[k].l+tree[k].r)>>1;
if (l<=mid) update (k*2,l,r,val);
if (r>mid) update (k*2+1,l,r,val);
tree[k].data=tree[k*2+1].data+tree[k*2].data;
}
inline int query (int k,int l,int r) {
if (l<=tree[k].l&&r>=tree[k].r) return tree[k].data;
lazydown (k);
int mid= (tree[k].l+tree[k].r)>>1;
int ans=0;
if (l<=mid) ans+=query (k*2,l,r);
if (r>mid) ans+=query (k*2+1,l,r);
tree[k].data=tree[k*2].data+tree[k*2+1].data;
return ans;
}
bool check (int mid) {
buildtree (1,1,n);
rep (i,1,n) {
if (a[i]>=mid) update (1,i,i,1);
else update (1,i,i,0);
}
rep (i,1,m) {
int x=query (1,ql[i],qr[i]);
if (op[i]==0) {
x=qr[i]-ql[i]+1-x;
update (1,ql[i],ql[i]+x-1,0);
update (1,ql[i]+x,qr[i],1);
}
else {
update (1,ql[i],ql[i]+x-1,1);
update (1,ql[i]+x,qr[i],0);
}
}
if (query (1,k,k)==1) return true;
return false;
}
inline void solve () {
scanf ("%d%d",&n,&m);
rep (i,1,n) scanf ("%d",&a[i]);
rep (i,1,m) {
scanf ("%d%d%d",&op[i],&ql[i],&qr[i]);
}
scanf ("%d",&k);
int l=1,r=n,ans=0;
while (l<=r) {
int mid=(l+r)>>1;
if (check (mid)) l=mid+1,ans=mid;
else r=mid-1;
}
cout<<ans<<endl;
}
int main () {
// freopen ("data.in","r",stdin);
int t;
cin>>t;
while (t--) {
solve ();
}
// fclose (stdin);
return 0;
}