dry_ @ 2023-09-12 21:33:34
#include<bits/stdc++.h>
using namespace std;
int n,m,l,r;
long long ans;
struct node
{
int l; int r;
long long num;
long long add;
}tree[800012];
int up1(int ind) { return ind << 1 ; }
int up2(int ind){return ind << 1 | 1;}
void build(int l,int r,int ind)
{
tree[ind].num = (r - l + 1);
tree[ind].l = l;
tree[ind].r = r;
if(l == r)return;
int mid = (l + r) >> 1;
build(l,mid,up1(ind));
build(mid + 1,r,up2(ind));
}
void check(int ind)
{
if(tree[ind].add)
{
tree [ up1(ind) ].num -= tree [ ind ].add * ( tree [ up1( ind ) ].r - tree [ up1( ind ) ].l + 1 );
tree [ up2(ind) ].num -= tree [ ind ].add * ( tree [ up2( ind ) ].r - tree [ up2( ind ) ].l + 1 );
tree [ up1(ind) ].add += tree[ind].add ; tree[up2(ind)].add += tree[ind].add ; tree[ind].add = 0 ;
if(tree[up1(ind)].num < 0)tree[up1(ind)].num = 0;if(tree[up2(ind)].num < 0)tree[up2(ind)].num = 0;
}
}
void amend(int l,int r,int ind)
{
if(l <= tree[ind].l && r >= tree[ind].r)
{tree[ind].num -= (tree[ind].r - tree[ind].l + 1);
tree[ind].add += 1; if(tree[ind].num < 0)
tree[ind].num = 0; return; } check(ind);
if(tree[up1(ind)].r >= l) amend(l,r,up1(ind));
if(tree[up2(ind)].l <= r) amend(l,r,up2(ind));
long long p1 = tree[up1(ind)].num;
long long p2 = tree[up2(ind)].num;
tree[ind].num = p1 + p2;
}
int main()
{
scanf("%d %d",&n,&m);
build(1,n,1);for(int i = 1;i <= m;i++)
{scanf("%d %d",&l,&r);if(l <= 0)l = 1;
if(r <= 0) r = 1; amend(l,r,1);
} printf("%lld\n",tree[1].num);
}
by dry_ @ 2023-09-12 21:36:26
哦对了,```cpp printf("%lld\n",tree[ind].num);
要写成```
printf("%lld\n",tree[ind].num + 1);
by tjtdrxxz @ 2023-09-16 21:52:15
已AC,少初始化了一个点...
by dry_ @ 2023-09-16 22:07:15
那个是我小号(回的时候用错了)