解释: 先留坑
题目: https://www.cometoj.com/contest/73/problem/D?problem_id=4120
- #include<bits/stdc++.h>
- using namespace std;
- #define se set<aa>
- #define it iterator
- #define lowbit(x) (x&(-x))
- typedef long long ll;
- const int M=5e5+5;
- int n,m,q;
- struct ope{
- ll l,r,val;
- }a[M];
- struct quer{
- ll l,r,id;
- }b[M];
- struct aa{
- ll l,r,val,id;
- };
- set<aa>s;
- bool cmp(quer x,quer y){
- return x.r<y.r;
- }
- bool operator <(aa a,aa b) {
- return a.r <b.r;
- }
- ll tree[M],ans[M];
- void add(ll x,ll y)
- {
- if(x == 0) return;
- for(;x <= n; x += lowbit(x))
- tree[x] += y;
- }
- ll Sum(ll x) {
- ll ans = 0;
- for(; x> 0; x -= lowbit(x))
- ans += tree[x];
- return ans;
- }
- void split(se::it id,ll x){
- ll l=id->l,r=id->r,val=id->val,_id=id->id;
- if(x<l||x>=r)
- return ;
- s.erase(id);
- s.insert((aa){l,x,val,_id});
- s.insert((aa){x+1,r,val,_id});
- }
- void Assign(ll l,ll r,ll val,ll id){
- se::it x=s.lower_bound((aa){0,l-1,0,0});
- split(x,l-1);
- se::it y=s.lower_bound((aa){0,r,0,0});
- split(y,r);
- x=s.lower_bound((aa){0,l,0,0});
- y=s.lower_bound((aa){0,r+1,0,0});
- for(se::it i=x;i!=y;){
- se::it j=i;
- i++;
- add(j->id,-((j->r)-(j->l)+1)*(j->val));
- s.erase(j);
- }
- s.insert((aa){l,r,val,id});
- add(id,(r-l+1)*val);
- }
- int main(){
- scanf("%d%d%d",&n,&m,&q);
- for(int i=1;i<=n;i++){
- scanf("%lld%lld%lld",&a[i].l,&a[i].r,&a[i].val);
- }
- for(ll i=1;i<=q;i++)
- scanf("%lld%lld",&b[i].l,&b[i].r),b[i].id=i;
- sort(b+1,b+1+q,cmp);
- s.insert((aa){1,m,0,0});
- for(int i=1;i<=q;i++){
- for(int j=b[i-1].r+1;j<=b[i].r;j++){
- Assign(a[j].l,a[j].r,a[j].val,j);
- }
- ans[b[i].id]=Sum(n)-Sum(b[i].l-1);
- }
- for(int i=1;i<=q;i++)
- printf("%lld\n",ans[i]);
- return 0;
- }
- View Code
来源: http://www.bubuko.com/infodetail-3282358.html