JZOJ4973. 回合游戲

2019-11-08 02:06:20

字體：大中小

供稿：網(wǎng)友

題目大意

給定一個N $N$ 個點的圖，初始圖中沒有邊。有Q $Q$ 個操作，每次操作添加一條權(quán)值為w $w$ 的邊，或者刪除當前圖中一條邊。每次操作后，都會有兩個人的在圖上輪流取點，若一條邊的兩個端點都屬于同一個人，那么這個人可以獲得這個權(quán)值的分數(shù)。先手希望自己與后手的分差盡可能大；后手希望自己與先手的分差盡可能小，求每次操作完的分差。

Data Constraint N,Q≤100000 $N,Q/leq100000$

題解

考慮一條邊如何貢獻，設(shè)當前邊的權(quán)值為w $w$ ，若我們將w/2 $w/2$ 分別加在兩個段點上，就可以發(fā)現(xiàn)，當兩端屬于同一人時，權(quán)值和恰好為w $w$ 否則差必定不變，這與題目相符。所以現(xiàn)在問題轉(zhuǎn)化為，求一個有序序列奇數(shù)項和與偶數(shù)項和的差。用權(quán)值線段樹維護區(qū)間內(nèi)奇數(shù)項的和與偶數(shù)項的和即可。

時間復(fù)雜度：O(nlogn) $O(nlogn)$

SRC

#include<cstdio>#include<cstdlib>#include<cstring>#include<iostream>#include<algorithm>using namespace std ;#define N 100000 + 10typedef long long ll ;const int MAXN = 2e9 ;struct Edge { int u , v , w ;} E[N] ;struct Tree { ll Sum[2] ; int Son[2] ; int Num ;} T[40*N] ;int Val[N] ;int n , Q , O , tot , Cnt = 1 ;int ans ;ll ret ;int NewNode() { ++ Cnt ; T[Cnt].Son[0] = T[Cnt].Son[1] = 0 ; T[Cnt].Sum[0] = T[Cnt].Sum[1] = 0 ; T[Cnt].Num = 0 ; return Cnt ;}void Merge( int v ) { int lv = T[v].Son[0] , rv = T[v].Son[1] ; T[v].Num = T[lv].Num + T[rv].Num ; T[v].Sum[0] = T[rv].Sum[0] ; T[v].Sum[1] = T[rv].Sum[1] ; if ( T[rv].Num & 1 ) T[v].Sum[0] += T[lv].Sum[1] , T[v].Sum[1] += T[lv].Sum[0] ; else T[v].Sum[0] += T[lv].Sum[0] , T[v].Sum[1] += T[lv].Sum[1] ;}void Delete( int v , int l , int r , int x ) { if ( !v ) return ; if ( l == r ) { if ( T[v].Num & 1 ) T[v].Sum[1] -= x ; else T[v].Sum[0] -= x ; T[v].Num -- ; return ; } int mid = (l + r) >> 1 ; if ( x <= mid ) Delete( T[v].Son[0] , l , mid , x ) ; else Delete( T[v].Son[1] , mid + 1 , r , x ) ; Merge( v ) ;}void Insert( int v , int l , int r , int x ) { if ( l == r ) { if ( T[v].Num & 1 ) T[v].Sum[0] += x ; else T[v].Sum[1] += x ; T[v].Num ++ ; return ; } int mid = (l + r) >> 1 ; if ( x <= mid ) { if ( !T[v].Son[0] ) T[v].Son[0] = NewNode() ; Insert( T[v].Son[0] , l , mid , x ) ; } else { if ( !T[v].Son[1] ) T[v].Son[1] = NewNode() ; Insert( T[v].Son[1] , mid + 1 , r , x ) ; } Merge( v ) ;}int main() { scanf( "%d%d%d" , &n , &Q , &O ) ; int lastans = 0 ; for (int i = 1 ; i <= Q ; i ++ ) { int op ; scanf( "%d" , &op ) ; if ( op == 0 ) { int k ; scanf( "%d" , &k ) ; if ( O ) k ^= lastans ; int u = E[k].u , v = E[k].v , w = E[k].w ; Delete( 1 , 1 , MAXN , Val[u] ) ; if ( u != v ) Delete( 1 , 1 , MAXN , Val[v] ) ; Val[u] -= w , Val[v] -= w ; if ( Val[u] ) Insert( 1 , 1 , MAXN , Val[u] ) ; if ( Val[v] && u != v ) Insert( 1 , 1 , MAXN , Val[v] ) ; } else { ++ tot ; int u , v , w ; scanf( "%d%d%d" , &u , &v , &w ) ; if ( O ) u ^= lastans , v ^= lastans ; if ( Val[u] ) Delete( 1 , 1 , MAXN , Val[u] ) ; if ( Val[v] && u != v ) Delete( 1 , 1 , MAXN , Val[v] ) ; Val[u] += w , Val[v] += w ; Insert( 1 , 1 , MAXN , Val[u] ) ; if ( u != v ) Insert( 1 , 1 , MAXN , Val[v] ) ; E[tot].u = u , E[tot].v = v , E[tot].w = w ; } ans = (T[1].Sum[1] - T[1].Sum[0]) / 2 ; lastans = ans ; 以上.