【权值线段树】HDU6703-array
传送门
题意是说给定一个排列，长度1e5，要求支持两种操作：
1. 把某个位置的数字+1e7
2. 给定r, k.查询与前r个数字不同的，并且大于等于k的，最小的数字。
经过分析，答案最大不可能超过n+1。这样的话，操作1其实相当于把这个数字从排列中删去。
用两棵权值线段树，每个点上存的是位置。
对每次2操作，在[k,n]区间里找最靠左的并且val[x]大于r的数。
对每次1操作，最开始是初始化一颗每个点值都是n+1的权值线段树，删掉一个数代表这个数字在区间内可以被使用了。所以在线段树上把点改为该位置。
同时2操作也要找[k,n]区间里最靠左而且val2[x]小于等于r的数。
两个数取最小就是答案。
同时还需记录区间最大最小值，以用来在查询的时候剪枝。
没有这个剪枝，查询会退化为n^2log(n)的，因为区间里可能每个数都会递归到底。
#pragma GCC optimize(2)
#include<bits/stdc++.h>
using namespace std;
#define ls(x) (x << 1)
#define rs(x) ((x << 1) + 1)
#define min(a,b) (a)<(b)?(a):(b)
const int maxn = 1e5 + 233;
struct Node{
int l, r, v;
}t1[maxn * 4], t2[maxn * 4];
int a[maxn], pos[maxn];
int n;
void build(int p, int l, int r)
{
if(l == r)
{
t1[p].l = l, t1[p].r =