记录编号	142288	评测结果	AAAAAAAAAA
题目名称	[HDOJ5140]Hun Gui Wei公司	最终得分	100
用户昵称	cstdio	是否通过	通过
代码语言	C++	运行时间	1.988 s
提交时间	2014-12-07 10:47:56	内存使用	48.00 MiB

#include<iostream>
#include<cstdio>
#include<algorithm>
#include<cstring>
#include<vector>
#include<queue>
#include<deque>
#include<set>
using namespace std;
typedef long long LL;
const int SIZEN=100010;
class NODE{//函数式线段树的节点
public:
    LL sum;
    int l,r;
    int lson,rson;
    void clear(int a,int b){
        l=a,r=b;
        sum=0;
        lson=rson=-1;
    }
};
NODE tree[SIZEN*20];
int tot=0;
int build(int l,int r){
    int x=tot++;
    tree[x].clear(l,r);
    if(l<r){
        int mid=(l+r)/2;
        tree[x].lson=build(l,mid);
        tree[x].rson=build(mid+1,r);
    }
    return x;
}
int change(int x,int a,LL t){
    if(x==-1) return -1;
    if(tree[x].l>a||tree[x].r<a) return x;
    int p=tot++;
    tree[p]=tree[x];
    NODE &now=tree[p];
    now.sum+=t;
    now.lson=change(now.lson,a,t);
    now.rson=change(now.rson,a,t);
    return p;
}
LL query(int x,int a,int b){
    if(x==-1) return 0;
    NODE &now=tree[x];
    if(now.l>b||now.r<a) return 0;
    if(now.l>=a&&now.r<=b) return now.sum;
    return query(now.lson,a,b)+query(now.rson,a,b);
}
class DSCT{
public:
    vector<int> s;
    vector<int> t;
    void clear(void){
        s.clear();t.clear();
    }
    void insert(int x){
        s.push_back(x);
    }
    void prepare(void){
        t.clear();
        sort(s.begin(),s.end());
        for(int i=0;i<s.size();i++){
            if(!i||s[i]!=s[i-1]) t.push_back(s[i]);
        }
    }
    int sgl_turn(int x){
        return lower_bound(t.begin(),t.end(),x)-t.begin()+1;
    }
    void turn(LL &a,LL &b){
        a=max(a,-1LL),b=min(b,1000000001LL);
        a=lower_bound(t.begin(),t.end(),(int)a)-t.begin()+1;
        b=upper_bound(t.begin(),t.end(),(int)b)-t.begin()-1+1;
    }
}DA;
class PERSON{
public:
    int S,L,A;
}P[SIZEN];
bool operator < (PERSON a,PERSON b){
    return a.L<b.L;
}
int N;
LL K;
int root[SIZEN]={0};
int Llis[SIZEN]={0};
void answer(void){
    LL L1,L2,A1,A2;
    //scanf("%I64d%I64d%I64d%I64d",&L1,&L2,&A1,&A2);
    scanf("%lld%lld%lld%lld",&L1,&L2,&A1,&A2);
    L1+=K;L2-=K;A1+=K;A2-=K;
    if(L1>L2) swap(L1,L2);
    if(A1>A2) swap(A1,A2);
    DA.turn(A1,A2);
    L1=lower_bound(Llis+1,Llis+1+N,L1)-Llis;
    L2=upper_bound(Llis+1,Llis+1+N,L2)-Llis-1;
    K=query(root[L2],A1,A2)-query(root[L1-1],A1,A2);
    if(L1>L2) K=0;
    //printf("%I64d\n",K);
    printf("%lld\n",K);
}
void prepare(void){
    K=0;
    DA.prepare();
    for(int i=1;i<=N;i++) P[i].A=DA.sgl_turn(P[i].A);
    sort(P+1,P+1+N);
    for(int i=1;i<=N;i++) Llis[i]=P[i].L;
    tot=0;
    root[0]=build(1,N);
    for(int i=1;i<=N;i++) root[i]=change(root[i-1],P[i].A,P[i].S);
}
bool read(void){
    if(scanf("%d",&N)==EOF) return false;
    DA.clear();
    for(int i=1;i<=N;i++){
        scanf("%d%d%d",&P[i].S,&P[i].L,&P[i].A);
        DA.insert(P[i].A);
    }
    return true;
}
int main(){
    freopen("hunguiwei.in","r",stdin);
    freopen("hunguiwei.out","w",stdout);
    while(read()){
        int M;
        prepare();
        scanf("%d",&M);
        while(M--) answer();
    }
    return 0;
}