Fork me on GitHub

Codeforces837G

Codeforces837G题解

题解:

  • 这题只要读懂了题意,开大了范围,看清了如何强制在线,就能很快AC(雾)。
  • (似乎是一道主席树模板题)。

代码:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
#include <bits/stdc++.h>
#define gc getchar()
#define mid (l+r>>1)
#define ll long long
#define mod 1000000000
#define M 30000009
#define N 200009
using namespace std;
ll n,tr[M][2],root[N],cnt,lson[M],rson[M];
ll read()
{
ll x=1;
char ch;
while (ch=gc,ch<'0'||ch>'9') if (ch=='-') x=-1;
ll s=ch-'0';
while (ch=gc,ch>='0'&&ch<='9') s=s*10+ch-'0';
return s*x;
}
void ins(ll &cur,ll l,ll r,ll x,ll y,ll k,ll last)
{
cur=++cnt;
lson[cur]=lson[last],rson[cur]=rson[last];
tr[cur][k]=tr[last][k]+y;
tr[cur][k^1]=tr[last][k^1];
if (l==r) return;
if (x<=mid) ins(lson[cur],l,mid,x,y,k,lson[last]);
else ins(rson[cur],mid+1,r,x,y,k,rson[last]);
}
ll qry(ll cur,ll l,ll r,ll L,ll R,ll k)
{
if (!cur) return 0;
if (L<=l&&R>=r) return tr[cur][k];
ll ret=0;
if (L<=mid) ret+=qry(lson[cur],l,mid,L,R,k);
if (R>mid) ret+=qry(rson[cur],mid+1,r,L,R,k);
return ret;
}
int main()
{
n=read();
for (ll i=1;i<=n;i++)
{
ll x1=read(),x2=read(),y1=read(),a=read(),b=read(),y2=read();
ins(root[i],0,mod,0,y1,0,root[i-1]);
ins(root[i],0,mod,x1+1,b-y1,0,root[i]);
ins(root[i],0,mod,x2+1,y2-b,0,root[i]);
ins(root[i],0,mod,x1+1,a,1,root[i]);
ins(root[i],0,mod,x2+1,-a,1,root[i]);
}
ll Ans=0;
ll q=read();
for (int i=1;i<=q;i++)
{
ll l=read(),r=read(),x=(read()+Ans)%mod;
ll Ans1=qry(root[r],0,mod,0,x,0)-qry(root[l-1],0,mod,0,x,0);
ll Ans2=qry(root[r],0,mod,0,x,1)-qry(root[l-1],0,mod,0,x,1);
//if (i==4999) x=200001;
printf("%lld\n",Ans=(Ans1+x*Ans2));
}
return 0;
}
-------------本文结束感谢您的阅读-------------

本文标题:Codeforces837G

文章作者:wzf2000

发布时间:2017年12月26日 - 10:12

最后更新:2017年12月26日 - 10:12

原始链接:https://wzf2000.github.io/2017/12/26/Codeforces837G/

许可协议: 署名-非商业性使用-禁止演绎 4.0 国际 转载请保留原文链接及作者。