#include <iostream> #include <stdio.h> #include <string.h> #include <stack> #include <queue> #include <map> #include <set> #include <vector> #include <math.h> #include <algorithm> using namespace std; #define ls 2*i #define rs 2*i+1 #define up(i,x,y) for(i=x;i<=y;i++) #define down(i,x,y) for(i=x;i>=y;i--) #define mem(a,x) memset(a,x,sizeof(a)) #define w(a) while(a) #define LL long long const double pi = acos(-1.0); #define N 100005 #define mod 19999997 const int INF = 0x3f3f3f3f; #define exp 1e-8 LL sum[1<<20],col[1<<20],ans[N]; int seg[N*4],len; bool flag[1<<20]; int n,m; struct brick { int l,r,lid,rid; }a[N]; struct board { int l,r,h,lid,rid,id; }b[N]; int cmp(board a,board b){ return a.h>b.h; } void push_down(int i,int l,int r) { int mid = (l+r)/2; if(col[i]) { col[ls] += col[i]; col[rs] += col[i]; sum[ls] += (LL)col[i]*(seg[mid+1]-seg[l]); sum[rs] += (LL)col[i]*(seg[r+1]-seg[mid+1]); col[i] = 0; } } void build(int i,int l,int r) { sum[i] = col[i] = 0; flag[i] = false; if(l==r) return; int mid = (l+r)/2; build(ls,l,mid); build(rs,mid+1,r); } void updata1(int L,int R,int val,int l,int r,int i) { if(L<=l && r<=R) { col[i]+=val; sum[i]+=val*(seg[r+1]-seg[l]); return; } push_down(i,l,r); int mid = (l+r)/2; if(L<=mid) updata1(L,R,val,l,mid,ls); if(R>mid) updata1(L,R,val,mid+1,r,rs); sum[i] = sum[ls]+sum[rs]; } void updata2(int L,int R,int l,int r,int i) { if(flag[i]) return; if(L<=l && r<=R) { flag[i] = true; sum[i]=0; return; } push_down(i,l,r); int mid = (l+r)/2; if(L<=mid) updata2(L,R,l,mid,ls); if(R>mid) updata2(L,R,mid+1,r,rs); sum[i] = sum[ls]+sum[rs]; } LL query(int L,int R,int l,int r,int i) { if(flag[i]) return 0; if(L<=l && r<=R) { return sum[i]; } push_down(i,l,r); int mid = (l+r)/2; LL ret = 0; if(L<=mid) ret+=query(L,R,l,mid,ls); if(R>mid) ret+=query(L,R,mid+1,r,rs); return ret; } int main() { int i,j,k; w(~scanf("%d%d",&n,&m)) { len = 0; up(i,0,n-1) { scanf("%d%d",&a[i].l,&a[i].r); seg[len++] = a[i].l; seg[len++] = a[i].r; } up(i,0,m-1) { scanf("%d%d%d",&b[i].l,&b[i].r,&b[i].h); b[i].id = i; seg[len++] = b[i].l; seg[len++] = b[i].r; } sort(seg,seg+len); len = unique(seg,seg+len)-seg; up(i,0,n-1) { a[i].lid = lower_bound(seg,seg+len,a[i].l)-seg; a[i].rid = lower_bound(seg,seg+len,a[i].r)-seg; } up(i,0,m-1) { b[i].lid = lower_bound(seg,seg+len,b[i].l)-seg; b[i].rid = lower_bound(seg,seg+len,b[i].r)-seg; } build(1,0,len-1); up(i,0,n-1) { updata1(a[i].lid,a[i].rid-1,1,0,len-1,1); } sort(b,b+m,cmp); up(i,0,m-1) { ans[b[i].id] = query(b[i].lid,b[i].rid-1,0,len-1,1); updata2(b[i].lid,b[i].rid-1,0,len-1,1); } up(i,0,m-1) printf("%lldn",ans[i]); printf("n"); } return 0; }
