WC2018集训吉老师的军训练

#include<bits/stdc++.h>

#define RG register

#define IL inline

#define _ 200005

#define X 100000000

#define ll unsigned long long

using namespace std;

IL int gi(){

	RG int data = 0 , m = 1; RG char ch = 0;

	while(ch != '-' && (ch<'0' || ch > '9')) ch = getchar();

	if(ch == '-'){m = 0; ch = getchar();}

	while(ch>='0' && ch<='9'){data = (data<<1) + (data<<3) + ch - '0' ;  ch = getchar();}

	return (m) ? data : -data ;

}

struct HJT{int ls,rs; ll sumK,sumB,tagK,tagB;}t[40*_] ;

struct YCB{

	int l,r,ps; ll dk,db;

	bool operator < (const YCB &B) const{

		return ps < B.ps ;

	}

}q[_<<1];

int tot,n,m,Q,X1,X2,Y1,Y2,d,xx,yy,Y[_],rt[_],oo,yoy; ll S,ans ; 

void Update(int &o,ll l,ll r,int ql,int qr,ll dk,ll db){

	t[++oo] = t[o]; o = oo ;

	if(ql <= l && r <= qr){

		t[o].tagK += dk ; t[o].tagB += db ;

		t[o].sumK += 1ll * (r - l + 1) * dk ;

		t[o].sumB += 1ll * (r - l + 1) * db ;

	    return ;

	}RG int mid = (l + r) >> 1;

	if(ql <= mid) Update(t[o].ls , l , mid , ql , qr , dk , db) ;

	if(qr  > mid) Update(t[o].rs , mid + 1 , r , ql , qr , dk , db) ;

	t[o].sumK = t[t[o].ls].sumK + t[t[o].rs].sumK + (r-l+1) * t[o].tagK ;

	t[o].sumB = t[t[o].ls].sumB + t[t[o].rs].sumB + (r-l+1) * t[o].tagB ;

}

ll Query(int &o,int l,int r,int ql,int qr,ll x){

	if(!o) return 0;

	if(ql == l && r == qr) return 1ll * t[o].sumK * x + t[o].sumB ;

	RG int mid = (l + r) >> 1;

	RG ll Data = (qr-ql+1) * ( t[o].tagK * x  + t[o].tagB );

	if(qr <= mid) return Data + Query(t[o].ls,l,mid,ql,qr,x) ;

	else if(ql > mid) return Data + Query(t[o].rs,mid+1,r,ql,qr,x) ;

	else return

			 Data +

			 Query(t[o].ls,l,mid,ql,mid,x) + Query(t[o].rs,mid+1,r,mid+1,qr,x) ;

	return 0;

}

int main(){

	freopen("c.in","r",stdin) ;

	freopen("c.out","w",stdout) ;

	n = gi(); m = gi(); d = gi(); Q = gi();

	for(RG int i = 1; i <= d; i ++){

		X1 = gi(); X2 = gi(); Y1 = gi(); Y2 = gi(); S = gi();

		q[++tot] = (YCB){X1 , X2 , Y1 , S , 1ll*S*(1-Y1)} ;

		q[++tot] = (YCB){X1 , X2 , Y2+1 , -S , 1ll*S*Y2 } ;

		Y[++yoy] = Y1 ; Y[++yoy] = Y2 + 1;

	}

	sort(q + 1 , q + tot + 1) ;

	sort(Y + 1 , Y + yoy + 1) ;

	rt[0] = ++ oo ;

	for(RG int i = 1; i <= tot; i ++)

		rt[i] = rt[i-1] , Update(rt[i] , 1 , X , q[i].l , q[i].r , q[i].dk , q[i].db) ;

	ans = 0;

	while(Q --){

		xx = gi(); yy = gi();

		X1 = ans % n + 1; X2 = (ans + xx) % n + 1 ;

		Y1 = ans % m + 1; Y2 = (ans + yy) % m + 1 ;

		if(X1 > X2) swap(X1 , X2) ;

		if(Y1 > Y2) swap(Y1 , Y2) ;

		xx = upper_bound(Y + 1 , Y + yoy + 1 , Y1 - 1) - Y - 1 ;

		yy = upper_bound(Y + 1 , Y + yoy + 1 , Y2) - Y - 1 ;

		ans = 0;

		ans = ans + Query(rt[yy] , 1 , X , X1 , X2 , Y2) ;

		ans = ans - Query(rt[xx] , 1 , X , X1 , X2 , Y1-1) ;

		printf("%llu",ans) ; puts("");

	}return 0;

}
巴特西

WC2018集训吉老师的军训练

WC2018集训吉老师的军训练

最新文章

热门文章

巴特西

WC2018集训 吉老师的军训练

WC2018集训 吉老师的军训练

最新文章

热门文章

WC2018集训吉老师的军训练

WC2018集训吉老师的军训练
