傳送門

文章目錄

• 題意：
• 思路：

題意：

給你一張$n$個(gè)點(diǎn)$m$條邊的圖，其中每個(gè)點(diǎn)$i$初始編號(hào)為$i$，邊是有向的，方向?yàn)閺木幪?hào)大的指向編號(hào)小的。定義一個(gè)貢獻(xiàn)為存在某三個(gè)點(diǎn)$a,b,c$有兩條邊為$a?>b,b?>c$，這個(gè)時(shí)候貢獻(xiàn)為$1$。有$q$個(gè)詢問(wèn)，每次給出一個(gè)點(diǎn)$x$，代表將$x$的編號(hào)變成最大。對(duì)于每次詢問(wèn)輸出當(dāng)前圖的貢獻(xiàn)。

思路：

首先需要知道如何快速的算出貢獻(xiàn)來(lái)。通過(guò)觀察不難發(fā)現(xiàn)，$b$作為一個(gè)中間點(diǎn)，他的$in[b]?out[b]$就是$b$作為中間點(diǎn)的貢獻(xiàn)。對(duì)于每個(gè)$i$求出來(lái)$in[i]?out[i]$即為初始的貢獻(xiàn)。
考慮對(duì)于每次修改，我們?nèi)绻芸焖俚恼业疆?dāng)前查詢的點(diǎn)$x$的入邊，那么問(wèn)題就好解決了。
我們可以重新開一個(gè)數(shù)組來(lái)記錄下來(lái)，但是實(shí)際上并沒(méi)有必要，我們發(fā)現(xiàn)直接將原圖建反邊，讓后直接跑當(dāng)前點(diǎn)的出邊，這樣就避免了刪除操作，非常巧妙。
這樣的時(shí)間復(fù)雜度也是正確的，題解有證明，比較長(zhǎng)就不多說(shuō)啦。
復(fù)雜度$O(q\sqrt{m})$

// 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,tune=native") //#pragma GCC optimize(2) #include<cstdio> #include<iostream> #include<string> #include<cstring> #include<map> #include<cmath> #include<cctype> #include<vector> #include<set> #include<queue> #include<algorithm> #include<sstream> #include<ctime> #include<cstdlib> #include<random> #include<cassert> #define X first #define Y second #define L (u<<1) #define R (u<<1|1) #define pb push_back #define mk make_pair #define Mid ((tr[u].l+tr[u].r)>>1) #define Len(u) (tr[u].r-tr[u].l+1) #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 pair<int,int> PII;const int N=1000010,mod=1e9+7,INF=0x3f3f3f3f; const double eps=1e-6;int n,m; vector<int>v[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 i=1;i<=m;i++) {int a,b; scanf("%d%d",&a,&b);if(a>b) v[b].pb(a),out[a]++,in[b]++;else v[a].pb(b),out[b]++,in[a]++;}for(int i=1;i<=n;i++) ans+=1ll*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]--;ans+=1ll*in[now]*out[now];v[now].pb(x);}out[x]+=in[x]; in[x]=0;v[x].clear();printf("%lld\n",ans);}return 0; } /**/

總結(jié)

以上是生活随笔為你收集整理的Codeforces Round #588 (Div. 2) F. Konrad and Company Evaluation 图论 + 建反图 好题的全部?jī)?nèi)容，希望文章能夠幫你解決所遇到的問(wèn)題。

如果覺(jué)得生活随笔網(wǎng)站內(nèi)容還不錯(cuò)，歡迎將生活随笔推薦給好友。