凤凰一级a做爰片免费网站,珠海响应式网站制作,重庆网站建设哪家公司哪家好,建筑工程公司名字起名大全2.逛公园I (parka) 【问题描述】 琥珀色黄昏像糖在很美的远方#xff0c;思念跟影子在傍晚一起被拉长…… 小 B 带着 GF 去逛公园#xff0c;公园一共有 n 个景点#xff0c;标号为 1 . . . n。景点之间有 m 条路径相连。 小 B 想选择编号在一段区间 [l, r] 内的…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的问题了 对于一个区间我们要求所有的合法的子区间所以我们可以求LL1……R为左端点的合法区间显然右端点要么是R要么是Right[i]所以我们可以二分出或者单调队列得到这个区间中恰好Right[i]大于R的点Pos Pos之前的点我们可以通过处理 i 到Right[i]区间长度的前缀和直接O1求到Pos之后显然合法右端点都是R可以等差数列做一做就是答案了。 如果全用单调队列复杂度可以降到很低 code 1 #includeiostream2 #includecstdio3 #includecmath4 #includealgorithm5 #includectime6 #define N 10000057 #define lc (p1)8 #define rc (p1|1)9 #define max(i,j) (ij?i:j)10 #define min(i,j) (ij?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].uu;20 e[cnt].vv;21 nxt[cnt]first[u];22 first[u]cnt;23 }24 struct T {25 int l,r,id;26 T() {27 l99999999;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 ifirst[x]; i; inxt[i]) {35 int ve[i].v;36 if(vprt[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 nowsiz0;43 int min0n1,max00;44 int tmp0;45 do{46 tmpstack[top--];47 nowsiz;48 max0max(max0,tmp);49 min0min(min0,tmp);50 }while(tmp!v);51 if(nowsiz1)continue;52 min0min(min0,x);53 max0max(max0,x);54 Lian[bcc].lmin0;55 Lian[bcc].rmax0;56 }57 } else low[x]min(low[x],dfn[v]);58 }59 }60 bool cmp(const Ta,const Tb) {61 return a.lb.l;62 }63 long long Right[N],Temp[N],Sum[N];64 int read() {65 int x0,f1;66 char cgetchar();67 while(!isdigit(c)) {68 if(c-)f-1;69 cgetchar();70 }71 while(isdigit(c)) {72 x(x3)(x1)c-0;73 cgetchar();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 nread(),mread();82 for(int i1; im; i) {83 int a,b;84 aread();85 bread();86 add(a,b);87 add(b,a);88 }89 for(int i1; in; i) {90 if(!dfn[i])tarjan(i);91 }92 sort(Lian1,Lianbcc1,cmp);93 for(int i1; ibcc; i) {94 Temp[i]Lian[i].l;95 }96 Min[bcc1]n1;97 for(int ibcc; i1; i--) {98 Min[i]min(Min[i1],Lian[i].r);99 }
100 for(int i1; in; i) {
101 int poslower_bound(Temp1,Tempbcc1,i)-Temp;
102 Right[i]Min[pos]-1;
103 Sum[i]Sum[i-1](Right[i]-i1);
104 }
105 int Q;
106 cinQ;
107 for(int i1; iQ; i) {
108 int L,R;
109 Lread(),Rread();
110 int poslower_bound(Right1,Rightn1,R)-Right;
111 if(posL)posL;
112 long long AnsSum[pos-1]-Sum[L-1];
113 Ans(long long)(R-pos1)*(long long)(R-pos2)/2;
114 coutAns\n;
115 }
116 return 0;
117 } over转载于:https://www.cnblogs.com/saionjisekai/p/9883881.html
