题解

1 条题解

  • 0
    @ 2017-11-07 17:24:20
    #include<iostream>  
    #include<cstdio>  
    #include<cstring>  
    #include<string>  
    #include<algorithm>  
    #include<cmath>  
    using namespace std;   
      
    int getint()  
    {  
        int i=0,f=1;char c;  
        for(c=getchar();(c<'0'||c>'9')&&c!='-';c=getchar());  
        if(c=='-')f=-1,c=getchar();  
        for(;c>='0'&&c<='9';c=getchar())i=(i<<3)+(i<<1)+c-'0';  
        return i*f;  
    }  
      
    const int N=1e5+5;  
    int n,m,tot,cnt,b[N*6];  
    long long bit[N*6],ans[N];  
    struct point  
    {  
        int x,y,val;  
        bool operator <(const point &a)const  
        {  
            return x==a.x?y<a.y:x<a.x;  
        }  
    }a[N];  
    struct question  
    {  
        int x1,x2,y1,y2;  
    }q[N];  
    struct halfquestion  
    {  
        int x,y1,y2,pos,k;  
        halfquestion(){}  
        halfquestion(int _x,int _y1,int _y2,int _pos,int _k):  
            x(_x),y1(_y1),y2(_y2),pos(_pos),k(_k){}  
        bool operator <(const halfquestion &a)const  
        {  
            return x<a.x;  
        }  
    }g[N<<1];  
      
    void lsh()  
    {  
        sort(b+1,b+cnt+1);  
        cnt=unique(b+1,b+cnt+1)-b-1;  
        for(int i=1;i<=n;i++)  
        {  
            a[i].x=lower_bound(b+1,b+cnt+1,a[i].x)-b;  
            a[i].y=lower_bound(b+1,b+cnt+1,a[i].y)-b;  
        }  
        for(int i=1;i<=m;i++)  
        {  
            q[i].x1=lower_bound(b+1,b+cnt+1,q[i].x1)-b;  
            q[i].y1=lower_bound(b+1,b+cnt+1,q[i].y1)-b;  
            q[i].x2=lower_bound(b+1,b+cnt+1,q[i].x2)-b;  
            q[i].y2=lower_bound(b+1,b+cnt+1,q[i].y2)-b;  
        }  
    }  
      
    void update(int x,int val)  
    {  
        for(int i=x;i<=cnt;i+=i&(-i))  
            bit[i]+=val;  
    }  
      
    long long query(int x)  
    {  
        long long res=0;  
        for(int i=x;i>0;i-=i&(-i))  
            res+=bit[i];  
        return res;  
    }  
      
    int main()  
    {  
        //freopen("lx.in","r",stdin);  
        n=getint(),m=getint();  
        for(int i=1;i<=n;i++)  
        {  
            b[++cnt]=a[i].x=getint();  
            b[++cnt]=a[i].y=getint();  
            a[i].val=getint();  
        }  
        for(int i=1;i<=m;i++)  
        {  
            b[++cnt]=q[i].x1=getint(),b[++cnt]=q[i].y1=getint();  
            b[++cnt]=q[i].x2=getint(),b[++cnt]=q[i].y2=getint();  
        }  
        lsh();  
        for(int i=1;i<=m;i++)  
        {  
            g[++tot]=halfquestion(q[i].x1-1,q[i].y1,q[i].y2,i,-1);  
            g[++tot]=halfquestion(q[i].x2,q[i].y1,q[i].y2,i,1);  
        }  
        sort(a+1,a+n+1);  
        sort(g+1,g+tot+1);  
        for(int i=1,j=1;i<=tot;i++)  
        {  
            while(j<=n&&a[j].x<=g[i].x)  
                update(a[j].y,a[j].val),j++;  
            ans[g[i].pos]+=(query(g[i].y2)-query(g[i].y1-1))*g[i].k;  
        }  
        for(int i=1;i<=m;i++)  
            printf("%lld\n",ans[i]);  
        return 0;  
    }  
    
    
  • 1

信息

难度
9
分类
(无)
标签
(无)
递交数
7
已通过
2
通过率
29%
上传者