E题，离线+树状数组

分析每一个位置i的数字A_{i什么时候会被删掉，在遇见第一个i < j并且 a_i > a_j时就要删掉，也就是说在询问区间[L,R]中，如果i>=L并且这个i对应的那个j<=R就需要计算一次贡献，构建一个record数组record[i]代表位置i所对应那个j在哪里。显然这个record可以倒着扫一遍+树状数组解决。每找到一个j就可以在位置j加一次贡献，那么最后计算答案的时候就是计算[L,R]区间被加了多少次贡献。最后的一个问题就是询问[L,R]区间的贡献但是有可能[1,L-1]的数字所对应的j在区间[L,R]里面，就会算多贡献。我自己的处理手法就是离线之后排序，按照询问区间的左端点从小到大排序，然后询问的左端点就慢慢变大，没改变一次左端点就把当前左端点之前的每个位置的贡献减去，就可以保证不会有贡献被多余的计算。}

int tree_Val[max_], limR,tree_Min[max_];
il int lowbit(int x) { return x & -x; }
void change(int x, int v,int *tree_) {
	while (x <= limR){
		tree_[x] += v;
		x += lowbit(x);
	}
}
int ask(int x, int* tree_) {
	int ans = 0;
	while (x > 0){
		ans += tree_[x];
		x -= lowbit(x);
	}
	return ans;
}
void change2(int x, int v, int* tree_) {
	while (x <= limR) {
		tree_[x] = min(tree_[x], v);
		x += lowbit(x);
	}
}
int ask2(int x, int* tree_) {
	int ans = inf;
	while (x > 0) {
		ans = min(ans, tree_[x]);
		x -= lowbit(x);
	}
	return ans;
}
int node[max_],vv[max_],vn,record[max_],ans[max_];
struct NN {
	int L, R, id;
} Que[max_];
bool cmp(NN& a, NN &b) {
	return a.L < b.L;
}
void solve() {
	int N = read(), Q = read();
	limR = N + 1;
	for (int i = 1; i <= N; i++)vv[i] = node[i] = read();
	sort(vv + 1, vv + 1 + N);
	vn = unique(vv + 1, vv + 1 + N) - vv - 1;
	for (int i = 1; i <= N; i++)node[i] = lower_bound(vv + 1, vv + 1 + vn, node[i]) - vv;
	memset(tree_Min, 127, sizeof(tree_Min));
	int ind;
	for (int i = N; i>= 1; i--) {
		ind = ask2(node[i] - 1, tree_Min);
		record[i] = ind;
		if (ind <= N)change(ind, 1, tree_Val);
		change2(node[i], i, tree_Min);
	}
	int L, R;
	for(int i = 1;i <= Q;i++){
		Que[i].L = read(), Que[i].R = read(); Que[i].id = i;
	}
	sort(Que + 1, Que + 1 + Q, cmp);
	int lasL = 0;
	for (int i = 1; i <= Q; i++) {
		for (int j = lasL + 1; j < Que[i].L; j++) {
			if (record[j] <= N)change(record[j], -1, tree_Val);
		}
		lasL = Que[i].L - 1;
		ans[Que[i].id] = ask(Que[i].R, tree_Val) - ask(Que[i].L - 1, tree_Val);
	}
	for (int i = 1; i <= Q; i++)	printf("%d\n", ans[i]);
}