JZOJ5919 逛公园

Description

     琥珀色黄昏像糖在很美的远方，思念跟影子在傍晚一起被拉长……
Description
  小 B 带着 GF 去逛公园，公园一共有 n 个景点，标号为 1 . . . n。景点之间有 m 条路径相连。
  小 B 想选择编号在一段区间 [l, r] 内的景点来游玩，但是如果这些景点的诱导子图形成了环，那么 GF 将会不高兴。
小 B 给出很多个询问 [x, y]，想让你求有多少个区间 [l, r] 满足 x ≤ l, r ≤ y 且不会使 GF不高兴。

Input

第一行为两个整数 n, m，表示景点和路径的数量。
第 2 . . . m + 1 行每行两个整数 ui, vi 表示第 i 路径的两端。
第 m + 2 行是一个整数 q 表示询问的个数，接下来 m 行每行两个整数 xi, yi 表示询问。

Output

q 行，每行一个整数表示答案。

Sample Input

Sample Output

27
8
19

Data Constraint

对于 30% 的数据，n, m ≤ 100。
对于另外 10% 的数据，n = m + 1。
对于另外 10% 的数据，n = m
对于 100% 的数据，n, m ≤ 3 × 10^5, xi ≤ yi，不存在重边、自环，不存在一条边同时存在于两个不同的简单环。

Hint

诱导子图：子图 G′ = (V′, E′)，原图 G = (V, E)。V′ 是 V 的子集，E′ = {(u, v)|u, v ∈V′,(u, v) ∈ E}

Solution

　　我们先 DFS 出图的每一个环，得到环上编号最小和最大的节点，那么合法的区间一定不能同时跨过这两个点。于是我们搞出一个 R 数组，R[i] 表示以 i 作为左端点时右端点最右可以到哪个位置。R 数组显然是单调递增的。

　　对于询问 l, r，我们二分出一个位置 i 满足 max-R[l . . . i − 1] ≤ r,min-R[i . . . r] ≥ r，直接计算即可，那么左边的贡献就可以用前缀和统计，右边就是一个等差数列。

 1 #include<cstdio>
 2 #define N 500007
 3 #define LL long long
 4 using namespace std;
 5 struct arr{
 6     int x,y,next;
 7 }edge[N*2];
 8 int n,m,q,ls[N];
 9 LL rr[N],a[N],r[N],f[N];
10 
11 LL max(LL x,LL y){
12     if (x>y) return x;
13     return y;
14 }
15 
16 LL min(LL x,LL y){
17     if (x<y) return x;
18     return y;
19 }
20 
21 int add(LL x,LL y,int e){
22     edge[e].x=x; edge[e].y=y;
23     edge[e].next=ls[edge[e].x]; ls[edge[e].x]=e;
24     edge[--e].x=y; edge[e].y=x;
25     edge[e].next=ls[edge[e].x]; ls[edge[e].x]=e;
26 }
27 
28 int ss(LL x,LL w,LL l){
29     a[w]=x;    
30     f[x]+=1;
31     if (f[x]!=1){
32         LL e=w,mi=x,ma=x;
33         while (a[e-1]!=x){
34             mi=min(mi,a[--e]);
35             ma=max(ma,a[e]);
36         }
37         if (r[mi]!=0) r[mi]=min(r[mi],ma);
38         else r[mi]=ma;
39         return 0;
40     }
41 
42     LL i=ls[x];
43     while (i!=0){
44         if (edge[i].y!=l){
45             ss(edge[i].y,w+1,x);
46             f[edge[i].y]-=1;
47         }
48         i=edge[i].next;
49     }
50 }
51 
52 int main(){
53     scanf("%d%d",&n,&m);
54     LL x,y;
55     for (int i=1;i<=m;i++){
56         scanf("%lld%lld",&x,&y);
57         add(x,y,i*2);
58     }
59     ss(1,1,0);
60     LL k=n;
61     for (int i=n;i>=1;i--){
62         if (r[i]!=0) k=min(r[i]-1,k);
63         r[i]=k;
64     }
65     for (int i=1;i<=n;i++)
66         rr[i]=rr[i-1]+(r[i]-i+1);
67     scanf("%d",&q);
68     for (int i=1;i<=q;i++){
69         scanf("%d%d",&x,&y);
70         LL lx=x,ly=y;
71         while (lx<ly){
72             LL mid=(lx+ly)/2;
73             if (r[mid]>=y)
74                 ly=mid;
75             else lx=mid+1;
76         }
77         if (r[lx]<y) lx++;
78         LL ans=1ll*(rr[lx-1]-rr[x-1]);
79         ans+=1ll*(y-lx+1)*(y-lx+2)/2;
80         printf("%lld
",ans);
81     }
82 }

View Code