求问

123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960616263646566676869707172737475767778798081828384#include <bits/stdc++.h>
#define ld p << 1
#define rd p << 1 | 1
using namespace std;
const int N = 2e5 + 5, M = 2e5 + 5;
inline int read(){
	int sum = 0;
	char ch = getchar();
	while(ch < '0' || ch > '9') ch = getchar();
	while(ch >= '0' && ch <= '9') sum = (sum << 1) + (sum << 3) + (ch ^ 48), ch = getchar();
	return sum;
}
int n, a[N], Q, tot, ans[M];
struct wt{
	int l, r, x, wz;
} b[M];
bool cmp(wt t1, wt t2){
	return t1.x > t2.x;
}
struct Node2{
	int sz, id;
} tmp[N];
bool cmp2(Node2 t1, Node2 t2){
	return t1.sz > t2.sz;
}
struct Node{
	int l, r, sum;
	bool pl, pr;
} t[N << 2];
void push_up(int p){
	t[p].sum = t[ld].sum + t[rd].sum - (t[ld].pr && t[rd].pl);
	t[p].pl = t[ld].pl, t[p].pr = t[rd].pr;
}
void build(int p, int l, int r){
	t[p] = (Node) {l, r, 0, 0, 0};
	if(l == r) return;
	int mid = l + r >> 1;
	build(ld, l, mid);
	build(rd, mid + 1, r);
	push_up(p);
}
void upd(int p, int l){
	if(l <= t[p].l && t[p].r <= l){
		t[p].sum = 1, t[p].pl = t[p].pr = 1;
		return;
	}
	int mid = t[p].l + t[p].r >> 1;
	if(l <= mid) upd(ld, l);
	if(l > mid) upd(rd, l);
	push_up(p);
}
Node ask(int p, int l, int r){
	if(l <= t[p].l && t[p].r <= r){
		return t[p];
	}
	int mid = t[p].l + t[p].r >> 1;
	Node ans = {0, 0, 0, 0, 0};
	if(l <= mid) ans = ask(ld, l, r);
	if(r > mid){
		Node kr = ask(rd, l, r);
		if(ans.l == 0) ans = ask(rd, l, r);
		else ans = {ans.l, kr.r, ans.sum + kr.sum - (ans.pr && kr.pl), ans.pl, kr.pr};
	}
	return ans;
}
int main(){
	ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);
	n = read(), Q = read();
    build(1, 1, n);
	for(int i = 1;i <= n;i++) a[i] = read(), tmp[i] = {a[i], i};
	sort(tmp + 1, tmp + n + 1, cmp2);
	for(int i = 1;i <= Q;i++){
		b[i].l = read(), b[i].r = read(), b[i].x = read();
		b[i].wz = i;
	}
	sort(b + 1, b + Q + 1, cmp);
	for(int i = 1;i <= Q;i++){
		int l = b[i].l, r = b[i].r, x = b[i].x;
		while(tot < n && tmp[tot + 1].sz > x) tot++, upd(1, tmp[tot].id);
		ans[b[i].wz] = ask(1, l, r).sum;
	}
	for(int i = 1;i <= Q;i++) cout << ans[i] << "\n";
	return 0;
}

123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960616263646566676869707172737475767778798081#include <bits/stdc++.h>
#define ld p << 1
#define rd p << 1 | 1
using namespace std;
const int N = 2e5 + 5, M = 2e5 + 5;
inline int read(){
	int sum = 0;
	char ch = getchar();
	while(ch < '0' || ch > '9') ch = getchar();
	while(ch >= '0' && ch <= '9') sum = (sum << 1) + (sum << 3) + (ch ^ 48), ch = getchar();
	return sum;
}
int n, a[N], Q, tot, ans[M];
struct wt{
	int l, r, x, wz;
} b[M];
bool cmp(wt t1, wt t2){
	return t1.x > t2.x;
}
struct Node2{
	int sz, id;
} tmp[N];
bool cmp2(Node2 t1, Node2 t2){
	return t1.sz > t2.sz;
}
struct Node{
	int l, r, sum;
	bool pl, pr;
} t[N << 2];
Node operator + (Node t1, Node t2){
	return (Node) {t1.l, t2.r, t1.sum + t2.sum - (t1.pr && t2.pl), t1.pl, t2.pr};
}
void push_up(int p){
	t[p] = t[ld] + t[rd];
}
void build(int p, int l, int r){
	t[p] = (Node) {l, r, 0, 0, 0};
	if(l == r) return;
	int mid = l + r >> 1;
	build(ld, l, mid);
	build(rd, mid + 1, r);
	push_up(p);
}
void upd(int p, int l){
	if(l <= t[p].l && t[p].r <= l){
		t[p].sum = 1, t[p].pl = t[p].pr = 1;
		return;
	}
	int mid = t[p].l + t[p].r >> 1;
	if(l <= mid) upd(ld, l);
	if(l > mid) upd(rd, l);
	push_up(p);
}
Node ask(int p, int l, int r){
	if(l <= t[p].l && t[p].r <= r){
		return t[p];
	}
	int mid = t[p].l + t[p].r >> 1;
	if(r <= mid) return ask(ld, l, r);
	if(l > mid) return ask(rd, l, r);
	return ask(ld, l, r) + ask(rd, l, r);
}
int main(){
	ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);
	n = read(), Q = read();
    build(1, 1, n);
	for(int i = 1;i <= n;i++) a[i] = read(), tmp[i] = {a[i], i};
	sort(tmp + 1, tmp + n + 1, cmp2);
	for(int i = 1;i <= Q;i++){
		b[i].l = read(), b[i].r = read(), b[i].x = read();
		b[i].wz = i;
	}
	sort(b + 1, b + Q + 1, cmp);
	for(int i = 1;i <= Q;i++){
		int l = b[i].l, r = b[i].r, x = b[i].x;
		while(tot < n && tmp[tot + 1].sz > x) tot++, upd(1, tmp[tot].id);
		ans[b[i].wz] = ask(1, l, r).sum;
	}
	for(int i = 1;i <= Q;i++) cout << ans[i] << "\n";
	return 0;
}