JZOJ4973. 回合游戏

2019-11-08 02:06:20

字体：大中小

来源：转载

供稿：网友

题目大意

给定一个N $N$ 个点的图，初始图中没有边。有Q $Q$ 个操作，每次操作添加一条权值为w $w$ 的边，或者删除当前图中一条边。每次操作后，都会有两个人的在图上轮流取点，若一条边的两个端点都属于同一个人，那么这个人可以获得这个权值的分数。先手希望自己与后手的分差尽可能大；后手希望自己与先手的分差尽可能小，求每次操作完的分差。

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

题解

考虑一条边如何贡献，设当前边的权值为w $w$ ，若我们将w/2 $w/2$ 分别加在两个段点上，就可以发现，当两端属于同一人时，权值和恰好为w $w$ 否则差必定不变，这与题目相符。所以现在问题转化为，求一个有序序列奇数项和与偶数项和的差。用权值线段树维护区间内奇数项的和与偶数项的和即可。

时间复杂度：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 ; PRintf( "%d/n" , ans ) ; }}

以上.

上一篇：关于C的一些小知识点

下一篇：求取得最高成绩同学人数