題干：

DZY has a sequence?a[1..n]a[1..n]. It is a permutation of integers?1～n1～n.?

Now he wants to perform two types of operations:?

0lr0lr: Sort?a[l..r]a[l..r]?in increasing order.?

1lr1lr: Sort?a[l..r]a[l..r]?in decreasing order.?

After doing all the operations, he will tell you a position?kk, and ask you the value of?a[k]a[k].?

Input

First line contains?tt, denoting the number of testcases.?

tt?testcases follow. For each testcase:?

First line contains?n,mn,m.?mm?is the number of operations.?

Second line contains?nn?space-separated integers?a[1],a[2],?,a[n]a[1],a[2],?,a[n], the initial sequence. We ensure that it is a permutation of?1～n1～n.?

Then?mm?lines follow. In each line there are three integers?opt,l,ropt,l,r?to indicate an operation.?

Last line contains?kk.?

(1≤t≤50,1≤n,m≤100000,1≤k≤n,1≤l≤r≤n,opt∈{0,1}1≤t≤50,1≤n,m≤100000,1≤k≤n,1≤l≤r≤n,opt∈{0,1}. Sum of?nn?in all testcases does not exceed?150000150000. Sum of?mm?in all testcases does not exceed?150000150000)?

Output

For each testcase, output one line - the value of?a[k]a[k]?after performing all?mmoperations.?

Sample Input

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

Sample Output

5

Hint

1 6 2 5 3 4 -> [1 2 5 6] 3 4 -> 1 2 [6 5 4 3] -> 1 [2 5 6] 4 3. At last $a[3]=5$.

題目大意：

解題報告：

兩個log的做法展現了二分答案的強大功能。首先二分枚舉第?k?位的值x，然后將大于等于x的數都變為?1?，小于x的數變為?0?，這樣這數字序列就變成了01序列，只有這兩種性質。我們用線段樹不難實現對?01?序列按要求進行排序，然后如果第?k?位為?1?說明x可以是ans但是太小了，要調整下界。就這樣不斷二分下來，得到的邊界值就是第?k?位真實的值。這個做法是離線的，有兩個log?，但代碼好實現。

這題巧妙之處：第一在于只有一次查詢，第二在于是n的全排列。（但是貌似不是全排列也可用類似的方法做。）

nlogn的神仙方法：https://www.cnblogs.com/Paulliant/p/10185235.html（線段樹分割）

AC代碼：

#include<cstdio> #include<iostream> #include<algorithm> #include<queue> #include<map> #include<vector> #include<set> #include<string> #include<cmath> #include<cstring> #define F first #define S second #define ll long long #define pb push_back #define pm make_pair using namespace std; typedef pair<int,int> PII; const int MAX = 2e5 + 5; int n,m; struct Node {int op,l,r;Node(){}Node(int op,int l,int r):op(op),l(l),r(r){} } nn[MAX]; int a[MAX],k; struct TREE {int l,r;int val,laz; } tree[MAX<<2]; int len(int cur) {return tree[cur].r - tree[cur].l + 1; } void pushup(int cur) {tree[cur].val = tree[cur*2].val + tree[cur*2+1].val; } void pushdown(int cur) {if(tree[cur].laz == -1) return ;//如果是0？？？則？？？ int tmp = tree[cur].laz;tree[cur].laz = -1;tree[cur*2].val = len(cur*2) * tmp;tree[cur*2+1].val = len(cur*2+1) * tmp;tree[cur*2].laz = tmp;tree[cur*2+1].laz = tmp; } void build(int l,int r,int cur,int key) {tree[cur].l = l;tree[cur].r = r;tree[cur].laz = -1;if(l == r) {tree[cur].val = a[l]>=key;return;}int m = (l+r)>>1;build(l,m,cur*2,key);build(m+1,r,cur*2+1,key);pushup(cur); } int query(int pl,int pr,int cur) {if(pl <= tree[cur].l && pr >= tree[cur].r) {return tree[cur].val;}pushdown(cur);int res = 0;if(pl <= tree[cur*2].r) res += query(pl,pr,cur*2);if(pr >= tree[cur*2+1].l) res += query(pl,pr,cur*2+1);return res; } void update(int pl,int pr,int cur,int val) {if(pl <= tree[cur].l && pr >= tree[cur].r) {tree[cur].laz = val;tree[cur].val = val * len(cur);return;}pushdown(cur);if(pl <= tree[cur*2].r) update(pl,pr,cur*2,val);if(pr >= tree[cur*2+1].l) update(pl,pr,cur*2+1,val);pushup(cur); } bool ok(int x) {build(1,n,1,x);for(int i = 1; i<=m; i++) {int l=nn[i].l,r=nn[i].r,op=nn[i].op;int tmp = query(l,r,1);if(tmp == r-l+1 || tmp == 0) continue;if(op == 1) {update(l,l+tmp-1,1,1);update(l+tmp,r,1,0);}else {update(r-tmp+1,r,1,1);update(l,r-tmp,1,0);}} return query(k,k,1) == 1; } int main() {int t;cin>>t;while(t--) {scanf("%d%d",&n,&m);for(int i = 1; i<=n; i++) scanf("%d",a+i);for(int op,x,y,i = 1; i<=m; i++) {scanf("%d%d%d",&op,&x,&y);nn[i] = Node(op,x,y);}scanf("%d",&k);int l = 1,r = n,mid = (l+r)>>1,ans;while(l<=r) {mid = (l+r)>>1;if(ok(mid)) ans=mid,l = mid+1;else r = mid-1;}printf("%d\n",ans);} return 0 ; }

?

總結

以上是生活随笔為你收集整理的【HDU - 5649】DZY Loves Sorting（线段树，区间更新区间查询，思维，01缩数变换，线段树分割）的全部內容，希望文章能夠幫你解決所遇到的問題。

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