MZ求条

#include<bits/stdc++.h>
using namespace std;
#define int long long
const int N=2e6+5;
int a[N];
int ans[N]; 
int seg[N<<2];
int lazy_tag[N<<2];
struct Node
{
    int l,x;
    int id;
}b[N<<1];
void pushdown(int x,int l,int r)
{
	int mid=l+r>>1;
	seg[x<<1]+=lazy_tag[x]*(mid-l+1);
	lazy_tag[x<<1]+=lazy_tag[x];
	seg[x<<1|1]+=lazy_tag[x]*(r-mid);
	lazy_tag[x<<1|1]+=lazy_tag[x];
	lazy_tag[x]=0;
} 
void build(int x,int l,int r)
{
	if(l==r)
	{
		seg[x]=a[l];
		return;	
	}	
	int mid=l+r>>1;
	build(x<<1,l,mid);
	build(x<<1|1,mid+1,r);
	seg[x]=seg[x<<1]+seg[x<<1|1];
} 
void update(int x,int l,int r,int L,int R,int k)
{
	if(L<=l&&r<=R)
	{
		seg[x]+=k*(r-l+1);
		lazy_tag[x]+=k;
		return;
	}
	pushdown(x,l,r);
	int mid=l+r>>1;
	if(L<=mid) update(x<<1,l,mid,L,R,k);
	if(R>mid) update(x<<1|1,mid+1,r,L,R,k);
	seg[x]=seg[x<<1]+seg[x<<1|1]; 
}
int query(int x,int l,int r,int L,int R)
{
	if(L<=l&&r<=R) return seg[x];
	pushdown(x,l,r);
	int mid=l+r>>1;
	int ans=0;
	if(L<=mid) ans+=query(x<<1,l,mid,L,R);
	if(R>mid) ans+=query(x<<1|1,mid+1,r,L,R);
	seg[x]=seg[x<<1]+seg[x<<1|1]; 
	return ans;
}
bool cmp(Node x,Node y)
{
    return x.l<y.l;
}
signed main()
{
	cin.tie(0)->sync_with_stdio(0);
	int n,m;
	cin>>n>>m;
	for(int i=1;i<=n;i++) cin>>a[i];
	for(int i=1;i<=m;i++) 
    {
        int x;
        cin>>b[(i-1)*2+1].l>>b[i*2].l>>x;
        b[(i-1)*2+1].l--;
        b[(i-1)*2+1].x=b[i*2].x=x;
        b[(i-1)*2+1].id=(i-1)*2+1;
        b[i*2].id=i*2;
    }
    sort(b+1,b+2*m+1,cmp);
    int id=1;
    for(int i=1;i<=2*m;i++) 
	{
		for(int j=id;j<=n;j++)
		{
			if(j>b[i].l) break;
			update(1,1,n,a[j],a[j],1);
			id++;
		}
		if(b[i].id&1) ans[b[i].id/2]-=query(1,1,n,1,b[i].x);
		else ans[b[i].id/2]+=query(1,1,n,1,b[i].x);
	}
	for(int i=1;i<=m;i++) cout<<ans[i]<<endl;
	return 0;
}