• 设为首页
  • 点击收藏
  • 手机版
    手机扫一扫访问
    迪恩网络手机版
  • 关注官方公众号
    微信扫一扫关注
    公众号

CF901C.BipartiteSegments

原作者: [db:作者] 来自: [db:来源] 收藏 邀请

n<=300000,m<=300000的图,图上只有奇环,q<=300000个询问每次问:一个区间内有多少个子区间,满足只保留编号在该区间的点以及他们之间的边,可以构成一个二分图。

终于走出了第一步。。Pi--从点i开始往前延伸最早到哪里就不是二分图了。由于这个数组是单调的,只要这个数组求出来就可以回答询问:每次回答询问时,输出$\sum_{i=L}^{R} Max(L-1,P_i)$即可。

然后就是这个数组怎么求了。。要支持删除点、插入点、查询是不是二分图。。LCT??并查集??动态图??懵逼。。。

然而题目有特殊性质。。只有奇环就是没有环套环的意思啦,如果有环套环肯定是有偶环的,然后在一个环内,最大编号a,最小编号b,那么相当于对$[a,n]$区间的P数组对b取个Max。

 1 #include<stdio.h>
 2 #include<string.h>
 3 #include<algorithm>
 4 #include<stdlib.h>
 5 //#include<queue>
 6 //#include<math.h>
 7 //#include<time.h>
 8 //#include<iostream>
 9 using namespace std;
10 
11 int n,m,q;
12 #define maxn 300011
13 #define maxm 600011
14 struct Edge{int to,next;};
15 struct Graph
16 {
17     Edge edge[maxm]; int first[maxn],le;
18     Graph() {le=2; memset(first,0,sizeof(first));}
19     void in(int x,int y) {Edge &e=edge[le]; e.to=y; e.next=first[x]; first[x]=le++;}
20     void insert(int x,int y) {in(x,y); in(y,x);}
21 }g,bg;
22 
23 #define LL long long
24 int p[maxn]; LL sum[maxn];
25 
26 int dfn[maxn],low[maxn],Time=0,sta[maxn],top=0,tag[maxn]; bool insta[maxn];
27 void tarjan(int x,int fa)
28 {
29 //    cout<<"tarjan"<<x<<endl;
30     dfn[x]=low[x]=++Time;
31     sta[++top]=x; insta[x]=1;
32     for (int i=g.first[x];i;i=g.edge[i].next)
33     {
34         const Edge &e=g.edge[i]; if (e.to==fa) continue;
35         if (!dfn[e.to]) tarjan(e.to,x),low[x]=min(low[x],low[e.to]);
36         else if (insta[e.to]) low[x]=min(low[x],dfn[e.to]);
37     }
38     if (dfn[x]==low[x])
39     {
40         int Min=0x3f3f3f3f,Max=0;
41         while (sta[top]!=x) Min=min(Min,sta[top]),Max=max(Max,sta[top]),insta[sta[top]]=0,top--;
42         Min=min(Min,x); Max=max(Max,x); top--; insta[x]=0;
43         if (Min!=Max) tag[Max]=max(tag[Max],Min);
44     }
45 }
46 
47 int main()
48 {
49     scanf("%d%d",&n,&m);
50     for (int i=1,x,y;i<=m;i++)
51     {
52         scanf("%d%d",&x,&y);
53         g.insert(x,y);
54     }
55     
56     for (int i=1;i<=n;i++) if (!dfn[i]) tarjan(i,0);
57     int now=0;
58     for (int i=1;i<=n;i++) now=max(now,tag[i]),p[i]=now;
59 //    for (int i=1;i<=n;i++) cout<<p[i]<<' ';cout<<endl;
60     
61     for (int i=1;i<=n;i++) sum[i]=sum[i-1]+p[i];
62     scanf("%d",&q);
63     while (q--)
64     {
65         int x,y; scanf("%d%d",&x,&y);
66         int L=x,R=y+1;
67         while (L<R)
68         {
69             const int mid=(L+R)>>1;
70             if (p[mid]>=x) R=mid;
71             else L=mid+1;
72         }
73         printf("%lld\n",-1ll*(x-1)*(L-x)-(sum[y]-sum[L-1])+1ll*(x+y)*(y-x+1)/2);
74     }
75     return 0;
76 }
View Code

 


鲜花

握手

雷人

路过

鸡蛋
该文章已有0人参与评论

请发表评论

全部评论

专题导读
上一篇:
C#中DataRow的初始化发布时间:2022-07-13
下一篇:
C语言枚举类型(Enum)深入理解发布时间:2022-07-13
热门推荐
阅读排行榜

扫描微信二维码

查看手机版网站

随时了解更新最新资讯

139-2527-9053

在线客服(服务时间 9:00~18:00)

在线QQ客服
地址:深圳市南山区西丽大学城创智工业园
电邮:jeky_zhao#qq.com
移动电话:139-2527-9053

Powered by 互联科技 X3.4© 2001-2213 极客世界.|Sitemap