zjnu1707 TOPOVI (map+模拟)

Description

Mirko is a huge fan of chess and programming, but typical chess soon became boring for him, so he started having fun with rook pieces. He found a chessboard with N rows and N columns and placed K rooks on it. Mirko’s game is made of the following rules:

1. Each rook’s power is determined by an integer.

2. A rook sees all the fields that are in his row or column except its own field.

3. We say that a field is attacked if the binary XOR of all the powers of the rooks that see the field is greater than 0.

Notice that the field a rook is at can be attacked or not. Initially, Mirko placed the rooks in a certain layout on the board and will make P moves. After each move, determine how many fields are attacked. Every rook can be moved to any free field on the whole
board (not only across column and row).

Input

The first line of input contains integers N, K, P (1 ≤ N ≤ 1 000 000 000, 1 ≤ K ≤ 100 000, 1 ≤ P ≤ 100 000). Each of the following K lines contains three integers R, C, X (1 ≤ R, C ≤ N, 1 ≤ X ≤ 1 000 000 000) which denote that initially there is a rook of power
X on the field (R, C). Each of the following P lines contains four integers R1, C1, R2, C2 (1 ≤ R1, C1, R2, C2 ≤ N) which denote that the rook has moved from field (R1, C1) to field (R2, C2). It is guaranteed that there will not be two rooks on one field at
any point.

Output

The output must consist of P lines, the k th line containing the total number of attacked fields after k moves.

Sample Input

2 2 2

1 1 1

2 2 1

2 2 2 1

1 1 1 2

2 2 2

1 1 1

2 2 2

2 2 2 1

1 1 1 2

3 3 4

1 1 1

2 2 2

2 3 3

2 3 3 3

3 3 3 1

1 1 1 2

3 1 3 2

Sample Output

4

0

4

2

6

7

7

题意：有n*n的矩阵，放了k只乌鸦，每一只乌鸦能看到和它所在位置同一行的和同一列的格子，除了它自己站的位置，有p次操作，每次操作把一只乌鸦从原来站的位置放到另外一个位置，问每次操作后被看到的次数的异或和不为0的格子总数。

思路：用map记录第i行，第j列的异或值以及异或值为i的行，列的个数，然后每次移动一个子后，考虑失去这一格子对应的值value后对总的sum的影响，再考虑这一格子变成value^value后的值。

#include<stdio.h>

#include<stdlib.h>

#include<string.h>

#include<math.h>

#include<vector>

#include<map>

#include<set>

#include<queue>

#include<stack>

#include<string>

#include<algorithm>

using namespace std;

typedef long long ll;

#define inf 600000

#define maxn 100050

ll sum;

int n;

map<int,int>rxor,cxor;  //rxor[i]=j map里第i行的异或值

map<int,int>rcnt,ccnt; //rcnt[i]=j异或值为i的行的个数

map<pair<int,int> ,int>mp;

void remove(int r,int c,int value)

{

    int i,j;

    sum-=n-ccnt[rxor[r] ];

    sum-=n-rcnt[cxor[c] ];

    if(rxor[r]!=cxor[c]){

        sum++;

    }

    rcnt[rxor[r] ]--;

    rxor[r]^=value;

    rcnt[rxor[r] ]++;

    ccnt[cxor[c] ]--;

    cxor[c]^=value;

    ccnt[cxor[c] ]++;

    sum+=n-ccnt[rxor[r] ];

    sum+=n-rcnt[cxor[c] ];

    if(rxor[r]!=cxor[c]){

        sum--;

    }

    mp[make_pair(r,c) ]^=value;

}

int main()

{

    int m,i,j,k,p;

    int r1,r2,c1,c2,value;

    while(scanf("%d%d%d",&n,&k,&p)!=EOF)

    {

        rcnt[0]=ccnt[0]=n;

        for(i=1;i<=k;i++){

            scanf("%d%d%d",&r1,&c1,&value);

            remove(r1,c1,value);

        }

        for(i=1;i<=p;i++){

            scanf("%d%d%d%d",&r1,&c1,&r2,&c2);

            value=mp[make_pair(r1,c1)];

            remove(r1,c1,value);

            remove(r2,c2,value);

            printf("%lld\n",sum);

        }

    }

    return 0;

}

巴特西

zjnu1707 TOPOVI (map+模拟)

最新文章

热门文章