RT,参考了第四篇题解的做法,虽然神是神奇,但是还是 WA 0pts 啊
#include <bits/stdc++.h>
using namespace std;
inline long long read() {
long long num = 0, nev = 1; char ch = getchar();
while (!isdigit(ch)) { if (ch=='-') nev = -1; ch = getchar(); }
while (isdigit(ch)) { num = (num<<1)+(num<<3)+(ch^48); ch = getchar(); }
return num * nev;
}
inline void print(const long long& x) {
if (x<0) {putchar('-'); print(-x); }
if(x<10) putchar(x+48);
else { print(x/10); putchar(x%10+'0'); }
}
const long long MAXN = 114514;
struct node {
int left, right;
int suml, sumr;
};
node tree[MAXN << 2];
long long n, m;
void build(int k, int l, int r)
{
tree[k].left = l;
tree[k].right = r;
if (l == r) return ;
int mid = l + r >> 1;
build(k << 1, l, mid);
build(k << 1 | 1, mid + 1, r);
return ;
}
void modify_start(int k, int x)
{
if (tree[k].left == tree[k].right)
{
tree[k].suml ++;
return ;
}
if (x > tree[k<<1].right) modify_start(k<<1 |1, x);
else modify_start(k << 1, x);
tree[k].suml = tree[k<<1].suml + tree[k<<1 | 1].suml;
return ;
}
void modify_end(int k, int x)
{
if (tree[k].left == tree[k].right)
{
tree[k].sumr ++;
return ;
}
if (x>tree[k<<1].right) modify_end(k << 1 |1, x);
else modify_end(k << 1, x);
tree[k].sumr = tree[k<<1].sumr + tree[k<<1 | 1].sumr;
return ;
}
long long query_start(int k, int l, int r)
{
if (r < tree[k].left || tree[k].right < l) {
return 0;
}
if (l <= tree[k].left && tree[k].right <= r) {
return tree[k].suml;
}
long long res = 0;
res += query_start(k<<1, l, r);
res += query_start(k<<1 | 1, l, r);
return res;
}
long long query_end(int k, int l, int r)
{
if (r > tree[k].left || tree[k].right < l) {
return 0;
}
if (l <= tree[k].left && tree[k].right <= r)
{
return tree[k].sumr;
}
long long res = 0;
res += query_end(k<<1, l, r);
res += query_end(k<<1 | 1, l, r);
return res;
}
int main()
{
n = read();
m = read();
build(1,1,n);
for (int i = 1; i <= m; i ++)
{
int op = read(), l = read(), r = read();
if (op == 1)
{
modify_start(1, l);
modify_end(1, r);
// for (int j = 1; j <= n<<2; j ++) cout << tree[j].suml << ' ';
// putchar('\n');
}
else
{
printf("%lld\n", query_start(1,1,r)-query_end(1,1,l-1));
}
}
return 0;
}
老规矩,悬赏一个贴贴(