化妆品网站开发背景,如何创立网站 优帮云,长沙网站优化推广,网站建设实战教程传送门 文章目录题意#xff1a;思路#xff1a;题意#xff1a;
给你一张nnn个点mmm条边的图#xff0c;其中每个点iii初始编号为iii#xff0c;边是有向的#xff0c;方向为从编号大的指向编号小的。定义一个贡献为存在某三个点a,b,ca,b,ca,b,c有两条边为a−b,b−…传送门
文章目录题意思路题意
给你一张nnn个点mmm条边的图其中每个点iii初始编号为iii边是有向的方向为从编号大的指向编号小的。定义一个贡献为存在某三个点a,b,ca,b,ca,b,c有两条边为a−b,b−ca-b,b-ca−b,b−c这个时候贡献为111。有qqq个询问每次给出一个点xxx代表将xxx的编号变成最大。对于每次询问输出当前图的贡献。
思路
首先需要知道如何快速的算出贡献来。通过观察不难发现bbb作为一个中间点他的in[b]∗out[b]in[b]*out[b]in[b]∗out[b]就是bbb作为中间点的贡献。对于每个iii求出来in[i]∗out[i]in[i]*out[i]in[i]∗out[i]即为初始的贡献。 考虑对于每次修改我们如果能快速的找到当前查询的点xxx的入边那么问题就好解决了。 我们可以重新开一个数组来记录下来但是实际上并没有必要我们发现直接将原图建反边让后直接跑当前点的出边这样就避免了删除操作非常巧妙。 这样的时间复杂度也是正确的题解有证明比较长就不多说啦。 复杂度O(qm)O(q\sqrt{m})O(qm)
// Problem: F. Konrad and Company Evaluation
// Contest: Codeforces - Codeforces Round #588 (Div. 2)
// URL: https://codeforces.com/contest/1230/problem/F
// Memory Limit: 256 MB
// Time Limit: 4000 ms
//
// Powered by CP Editor (https://cpeditor.org)//#pragma GCC optimize(Ofast,no-stack-protector,unroll-loops,fast-math)
//#pragma GCC target(sse,sse2,sse3,ssse3,sse4.1,sse4.2,avx,avx2,popcnt,tunenative)
//#pragma GCC optimize(2)
#includecstdio
#includeiostream
#includestring
#includecstring
#includemap
#includecmath
#includecctype
#includevector
#includeset
#includequeue
#includealgorithm
#includesstream
#includectime
#includecstdlib
#includerandom
#includecassert
#define X first
#define Y second
#define L (u1)
#define R (u1|1)
#define pb push_back
#define mk make_pair
#define Mid ((tr[u].ltr[u].r)1)
#define Len(u) (tr[u].r-tr[u].l1)
#define random(a,b) ((a)rand()%((b)-(a)1))
#define db puts(---)
using namespace std;//void rd_cre() { freopen(d://dp//data.txt,w,stdout); srand(time(NULL)); }
//void rd_ac() { freopen(d://dp//data.txt,r,stdin); freopen(d://dp//AC.txt,w,stdout); }
//void rd_wa() { freopen(d://dp//data.txt,r,stdin); freopen(d://dp//WA.txt,w,stdout); }typedef long long LL;
typedef unsigned long long ULL;
typedef pairint,int PII;const int N1000010,mod1e97,INF0x3f3f3f3f;
const double eps1e-6;int n,m;
vectorintv[N];
int in[N],out[N];
LL ans;int main()
{
// ios::sync_with_stdio(false);
// cin.tie(0);scanf(%d%d,n,m);for(int i1;im;i) {int a,b; scanf(%d%d,a,b);if(ab) v[b].pb(a),out[a],in[b];else v[a].pb(b),out[b],in[a];}for(int i1;in;i) ans1ll*in[i]*out[i];printf(%lld\n,ans);int q; scanf(%d,q);while(q--) {int x; scanf(%d,x);ans-1ll*in[x]*out[x];for(auto now:v[x]) {ans-1ll*in[now]*out[now];in[now]; out[now]--;ans1ll*in[now]*out[now];v[now].pb(x);}out[x]in[x]; in[x]0;v[x].clear();printf(%lld\n,ans);}return 0;
}
/**/
