BZOJ4822[Cqoi2017]老C的任务——树状数组(二维数点)

#include<set>
#include<map>
#include<queue>
#include<stack>
#include<cmath>
#include<vector>
#include<cstdio>
#include<cstring>
#include<iostream>
#include<algorithm>
#define ll long long
using namespace std;
struct node
{
    int x;
    int y;
    int num;
    int cnt;
    int v;
}s[10000010];
int n,m;
ll v[10000010];
int a,b,c,d;
int g[10000010];
int maxy;
int tot;
ll ans[2000010][5];
void add(int x,int k)
{
    for(int i=x;i<=maxy;i+=i&-i)
    {
        v[i]+=1ll*k;
    }
}
ll ask(int x)
{
    ll res=0;
    for(int i=x;i;i-=i&-i)
    {
        res+=v[i];
    }
    return res;
}
bool cmp(node a,node b)
{
    if(a.x==b.x)
    {
        if(a.y==b.y)
        {
            return a.cnt<b.cnt; 
        }
        return a.y<b.y;
    }
    return a.x<b.x;
}
int main()
{
    scanf("%d%d",&n,&m);
    for(int i=1;i<=n;i++)   
    {
        scanf("%d%d%d",&s[i].x,&s[i].y,&s[i].v);
        g[i]=s[i].y;
    }
    tot=n;
    for(int i=1;i<=m;i++)
    {
        scanf("%d%d%d%d",&a,&b,&c,&d);
        s[++tot].x=a-1;
        s[tot].y=b-1;
        s[tot].cnt=i;
        s[tot].num=1;
        g[tot]=b-1;
        s[++tot].x=a-1;
        s[tot].y=d;
        s[tot].cnt=i;
        s[tot].num=2;
        g[tot]=d;
        s[++tot].x=c;
        s[tot].y=b-1;
        s[tot].cnt=i;
        s[tot].num=3;
        g[tot]=b-1;
        s[++tot].x=c;
        s[tot].y=d;
        s[tot].cnt=i;
        s[tot].num=4;
        g[tot]=d;
    }
    sort(g+1,g+1+tot);
    sort(s+1,s+1+tot,cmp);
    maxy=unique(g+1,g+1+tot)-g-1;
    for(int i=1;i<=tot;i++)
    {
        if(!s[i].cnt)
        {
            int val=lower_bound(g+1,g+1+maxy,s[i].y)-g;
            add(val,s[i].v);
        }
        else
        {
            int val=lower_bound(g+1,g+1+maxy,s[i].y)-g;
            ans[s[i].cnt][s[i].num]=ask(val);
        }
    }
    for(int i=1;i<=m;i++)
    {
        printf("%lld\n",ans[i][4]+ans[i][1]-ans[i][2]-ans[i][3]);
    }
}