2.逛公園I
?(parka)
?
【問題描述】
? ? ??琥珀色黃昏像糖在很美的遠方，思念跟影子在傍晚一起被拉長……
? ? ??小 B 帶著 GF 去逛公園，公園一共有 n 個景點，標號為 1 . . . n。景點之間有 m 條路徑相連。
? ? ??小 B 想選擇編號在一段區間 [l, r] 內的景點來游玩，但是如果這些景點的誘導子圖形成了環，那么 GF 將會不高興。
? ? ? 小 B 給出很多個詢問 [x, y]，想讓你求有多少個區間 [l, r] 滿足 x ≤ l, r ≤ y 且不會使 GF不高興。
【輸入】
第一行為兩個整數 n, m，表示景點和路徑的數量。
第 2 . . . m + 1 行每行兩個整數 ui, vi 表示第 i 路徑的兩端。
第 m + 2 行是一個整數 q 表示詢問的個數，接下來 m 行每行兩個整數 xi, yi 表示詢問。
【輸出】
q 行，每行一個整數表示答案。
【樣例輸入】
8 9
1 2
2 3
3 1
4 5
5 6
6 7
7 8
8 4
7 2
3
1 8
1 4
3 8
【樣例輸出】
27
8
19
?
【數據范圍與約定】
對于 30% 的數據，n, m ≤ 100。
對于另外 10% 的數據，n = m + 1。
對于另外 10% 的數據，n = m
對于 100% 的數據，n, m ≤ 3 × 10^5, xi ≤ yi，不存在重邊、自環，不存在一條邊同時存在于兩個不同的簡單環。
提示誘導子圖：
子圖 G′ = (V′, E′)，原圖 G = (V, E)。V′ 是 V 的子集，E′ = {(u, v)|u, v ∈V′,(u, v) ∈ E}
?
?
?
?
本人&正解思路：
首先如果中間有個環并且為誘導子圖，那么這個環的所有編號都在這個區間里面，顯然如果我們包含這個環的編號最大最小值，就包括了這個環，如果缺了其中之一都不能說是在區間里面的誘導環
所以我們要先求點雙聯通分量，因為一個點可以在多個環里面
所以我們就可以知道轉化成了這個問題，給定n條線段，每次詢問一個區間中至少多少個子區間是不同時包括n條線段任何一條的左右端點的。
所以我們要考慮對于一個點它最遠能延伸的地方
對于一個位置 i ，如果一條線段的左端點比它小顯然這條線段是不會影響這個點的，因為它大于左端點所以不會覆蓋這個整條線段
所以我們先把線段按左端點進行排序。
我們又知道這個最遠的值Right[i]肯定是左端點比 i 大的某條線段右端點恰好左邊一個的位置，也就是求左端點比 i 大的線段右端點的最小值
顯然如果我們直接枚舉肯定是不行的，所以我們可以倒序枚舉排序后的線段，預處理出第 i 條線段以及之后比它左端點大的線段的右端點的最小值（有點繞）
所以我們在找點 i 的Right[i]的時候我們可以二分排序線段左端點的值，也就是恰好左端點比它大的線段，直接就可以知道右端點最小是多少了
然后就是處理區間L-R的問題了
對于一個區間我們要求所有的合法的子區間，所以我們可以求L，L+1，……R為左端點的合法區間，顯然右端點要么是R，要么是Right[i]，所以我們可以二分出或者單調隊列得到這個區間中恰好Right[i]大于R的點Pos
Pos之前的點我們可以通過處理 i 到Right[i]區間長度的前綴和直接O（1）求到，Pos之后顯然合法右端點都是R，可以等差數列做一做，就是答案了。
如果全用單調隊列復雜度可以降到很低
code：
1 #include<iostream> 2 #include<cstdio> 3 #include<cmath> 4 #include<algorithm> 5 #include<ctime> 6 #define N 1000005 7 #define lc (p<<1) 8 #define rc (p<<1|1) 9 #define max(i,j) (i>j?i:j) 10 #define min(i,j) (i<j?i:j) 11 using namespace std; 12 int mx[N],mn[N]; 13 int n,m; 14 struct node { 15 int u,v; 16 } e[N]; 17 int first[N],nxt[N],cnt; 18 void add(int u,int v) { 19 e[++cnt].u=u; 20 e[cnt].v=v; 21 nxt[cnt]=first[u]; 22 first[u]=cnt; 23 } 24 struct T { 25 int l,r,id; 26 T() { 27 l=99999999; 28 } 29 } Lian[N],q[N]; 30 int low[N],top,bcc,dfn[N],siz[N],sign,stack[N],prt[N]; 31 void tarjan(int x) { 32 low[x]=dfn[x]=++sign; 33 stack[++top]=x; 34 for(int i=first[x]; i; i=nxt[i]) { 35 int v=e[i].v; 36 if(v==prt[x])continue; 37 if(!dfn[v]) { 38 prt[v]=x; 39 tarjan(v); 40 low[x]=min(low[x],low[v]); 41 if(low[v]>=dfn[x]){ 42 int nowsiz=0; 43 int min0=n+1,max0=0; 44 int tmp=0; 45 do{ 46 tmp=stack[top--]; 47 nowsiz++; 48 max0=max(max0,tmp); 49 min0=min(min0,tmp); 50 }while(tmp!=v); 51 if(nowsiz==1)continue; 52 min0=min(min0,x); 53 max0=max(max0,x); 54 Lian[++bcc].l=min0; 55 Lian[bcc].r=max0; 56 } 57 } else low[x]=min(low[x],dfn[v]); 58 } 59 } 60 bool cmp(const T&a,const T&b) { 61 return a.l<b.l; 62 } 63 long long Right[N],Temp[N],Sum[N]; 64 int read() { 65 int x=0,f=1; 66 char c=getchar(); 67 while(!isdigit(c)) { 68 if(c=='-')f=-1; 69 c=getchar(); 70 } 71 while(isdigit(c)) { 72 x=(x<<3)+(x<<1)+c-'0'; 73 c=getchar(); 74 } 75 return x*f; 76 } 77 long long Min[1000006]; 78 int main() { 79 // freopen("10.in","r",stdin); 80 // freopen("parka.out","w",stdout); 81 n=read(),m=read(); 82 for(int i=1; i<=m; i++) { 83 int a,b; 84 a=read(); 85 b=read(); 86 add(a,b); 87 add(b,a); 88 } 89 for(int i=1; i<=n; i++) { 90 if(!dfn[i])tarjan(i); 91 } 92 sort(Lian+1,Lian+bcc+1,cmp); 93 for(int i=1; i<=bcc; i++) { 94 Temp[i]=Lian[i].l; 95 } 96 Min[bcc+1]=n+1; 97 for(int i=bcc; i>=1; i--) { 98 Min[i]=min(Min[i+1],Lian[i].r); 99 } 100 for(int i=1; i<=n; i++) { 101 int pos=lower_bound(Temp+1,Temp+bcc+1,i)-Temp; 102 Right[i]=Min[pos]-1; 103 Sum[i]=Sum[i-1]+(Right[i]-i+1); 104 } 105 int Q; 106 cin>>Q; 107 for(int i=1; i<=Q; i++) { 108 int L,R; 109 L=read(),R=read(); 110 int pos=lower_bound(Right+1,Right+n+1,R)-Right; 111 if(pos<=L)pos=L; 112 long long Ans=Sum[pos-1]-Sum[L-1]; 113 Ans+=(long long)(R-pos+1)*(long long)(R-pos+2)/2; 114 cout<<Ans<<'\n'; 115 } 116 return 0; 117 }
over
)
