WC2018集训 吉老师的军训练
#include
#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 returnData +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;
}