题目链接
题外话:
这题应该没有蓝题难度吧,就是道树状数组模板题+一些小思维
利用前缀和思想,答案很明显为 \(r\) 之前的区间总数- \(l\) 之前的区间总数,即 \(r\) 之前的左端点数目- \(l\) 之前的右端点数目。分别用两个树状数组维护即可。
时间复杂度 \(O(n\log_2n)\)。
// Problem: P2184 贪婪大陆
// Contest: Luogu
// URL: https://www.luogu.com.cn/problem/P2184
// Memory Limit: 125 MB
// Time Limit: 1000 ms
//
// Powered by CP Editor (https://cpeditor.org)
#include<bits/stdc++.h>
using namespace std;
//#define int long long
inline int read(){int x=0,f=1;char ch=getchar();
while(ch<'0'||ch>'9'){if(ch=='-')f=-1;
ch=getchar();}while(ch>='0'&&ch<='9'){x=(x<<1)+
(x<<3)+(ch^48);ch=getchar();}return x*f;}
//#define mo
#define N 100010
int n, m, i, j, k;
int op, l, r;
int cntl[N], cntr[N];
void pshl(int x)
{
while(x<=n)
{
cntl[x]++;
x+=x&-x;
}
}
void pshr(int x)
{
while(x<=n)
{
cntr[x]++;
x+=x&-x;
}
}
int fndl(int x)
{
int ans=0;
while(x)
{
ans+=cntl[x];
x-=x&-x;
}
return ans;
}
int fndr(int x)
{
int ans=0;
while(x)
{
ans+=cntr[x];
x-=x&-x;
}
return ans;
}
signed main()
{
// freopen("tiaoshi.in", "r", stdin);
// freopen("tiaoshi.out", "w", stdout);
n=read(); m=read();
for(i=1; i<=m; ++i)
{
op=read(); l=read(); r=read();
if(op==1) pshl(l), pshr(r);
if(op==2) printf("%lld\n", fndl(r)-fndr(l-1));
}
return 0;
}