P2184 贪婪大陆

题面:https://www.luogu.org/problem/P2184

本题要求的是[l,r]内满足0<s<=r,s<=t<=r的(s,t)个数.
所以我们可以统计1~r内s的个数和1~l内t的个数
然后将二者相减即可得到答案.
因为满足条件的(s,t)会在r之前开始,在l之后结束.

Code:
#include<iostream>
#include<cstdio>
#include<cstring>
#include<cmath>
#include<algorithm>
using namespace std;
const int N=1000005;
int n,m,l[N],r[N];
int lowbit(int x){
    return x&-x;
}
void addl(int x,int p){
    while(x<=n){
        l[x]+=p;
        x+=lowbit(x);
    }
}
int suml(int x){
    int sum=0;
    while(x>0){
        sum+=l[x];
        x-=lowbit(x);
    }
    return sum;
}
void addr(int x,int p){
    while(x<=n){
        r[x]+=p;
        x+=lowbit(x);
    }
}
int sumr(int x){
    int sum=0;
    while(x>0){
        sum+=r[x];
        x-=lowbit(x);
    }
    return sum;
}
int main(){
    int opt,s,t;
    scanf("%d%d",&n,&m);
    for(int i=1;i<=m;i++){
        scanf("%d%d%d",&opt,&s,&t);
        if(opt==1){
            addl(s,1);
            addr(t,1);
        }
        else{
            printf("%d\n",suml(t)-sumr(s-1));
        }
    }
    return 0;
}