[hash][差分][虚树]JzojP6011天天爱跑步

 1 #include 
 2 #include 
 3 #define ll long long
 4 #define M 4000010
 5 #define N 50010
 6 #define mo 19260817
 7 #define Hash 4000
 8 using namespace std;
 9 struct edge { int to,from; }e[M];
10 struct node { ll l,r; }Q[M];
11 int n,cnt,tot,hash[mo],f[M],P[2*N],p[N],q[N],head[M],L[M],R[M],bz[Hash+10][Hash+10];
12 ll ans,x,y;
13 bool cmp1(int x,int y) { return Q[x].l<Q[y].l; }
14 bool cmp2(int x,int y) { return Q[x].r<Q[y].r; }
15 int gethash(ll x,ll y)
16 {
17     if (x<=Hash&&y<=Hash)
18     {
19         if (!bz[x][y]) bz[x][y]=++tot,Q[tot]=(node){x,y};
20         return bz[x][y];
21     }
22     int p=(x%mo*20+y%mo*11)%mo;
23     while (hash[p]&&(Q[hash[p]].l!=x||Q[hash[p]].r!=y)) p=(p+1)%mo;
24     if (!hash[p]) hash[p]=++tot,Q[tot]=(node){x,y};
25     return hash[p];
26 }
27 int insert(ll x,ll y)
28 {
29     int p=gethash(x,y),q=0;
30     if (x&&y)
31     {
32         if (x0)?insert(x,x):insert(x,y%x); else q=insert(x%y,y);
33         e[++cnt].to=p,e[cnt].from=head[q],head[q]=cnt;
34     }
35     return p;
36 }
37 void calc(ll x,ll y)
38 {
39     if (!x) return;
40     calc(L[x],(Q[L[x]].l-Q[x].l)/Q[x].r);
41     if (Q[x].l) calc(R[x],(Q[R[x]].r-Q[x].r)/Q[x].l);
42     f[x]+=f[L[x]]+f[R[x]],ans+=y*abs(f[x]);
43 }
44 int main()
45 {
46     freopen("a.in","r",stdin),freopen("a.out","w",stdout),scanf("%d",&n);
47     for (int i=1;i<=n;i++) scanf("%lld%lld",&x,&y),p[i]=insert(x,y);
48     for (int i=1;i<=n;i++) scanf("%lld%lld",&x,&y),q[i]=insert(x,y);
49     for (int i=1;i<=tot;i++)
50     {
51         P[P[0]=1]=i; for (int j=head[i];j;j=e[j].from) P[++P[0]]=e[j].to;
52         if (Q[i].l1,P+P[0]+1,cmp1); else sort(P+1,P+P[0]+1,cmp2);
53         for (int j=2;j<=P[0];j++) if (P[j]^P[j-1]) if (Q[i].l1]]=P[j]; else R[P[j-1]]=P[j];
54     }
55     for (int i=1;i<=n;i++) f[p[i]]++,f[q[i]]--;
56     for (int i=1;i<=tot;i++) if (!Q[i].l) calc(i,0);
57     printf("%lld",ans);
58 }