修改 - histcat

题目#

給定一個長度為 $n$ 的序列，第 $i$ 個元素的下標為 $i$，值為 $a_i$

現有 $q$ 次操作，每次給定一個區間 $[l,r]$，求該區間的元素和，並將區間內的所有元素值修改為 $0$

需要你輸出所有操作答案的異或和

由於 $n, q$ 很大，我們提供另外一種讀入方式

給定一個 $z$，注意其類型為 unsigned int，你需要調用 $n$ 次 $gen ()$ 函數獲得序列，再調用 $2n$ 次獲得每次操作的 $l,r$，具體代碼如下：

const int N = 1e9;
const int maxn = 1e7 + 10;
unsigned int x = 123456789, y = 362436069, z, a[maxn];
int n, q;
unsigned int gen()
{
    unsigned int t;
    x ^= x << 16; x ^= x >> 5; x ^= x << 1;
    t = x; x = y; y = z; z = t ^ x ^ y;
    return z % N + 1;
}

int main()
{
    scanf("%d%d%u", &n, &q, &z);
    for ( int i = 1; i <= n; ++ i ) 
        a[i] = gen();
    for ( int i = 1; i <= q; ++ i ) 
    {
        int l = gen() % n + 1, r = gen() % n + 1;
        if ( l > r ) swap(l, r);
        // do your things ...
    }
}

對於 $40%$ 的數據，滿足 $n, q\le 10^6$

對於 $100%$ 的數據，滿足 $n, q\leq 10^7$

题解#

~~我才不會告訴你考場上我想了 1 個小時還沒想出來~~

開始想到線段樹，看數據範圍，妥妥超時

~~然後就不知道怎麼做了~~

既然查詢完接著刪除，那麼一個數查詢完之後接著就可以不用管了

考慮用並查集維護不用管的數，開始的時候開 $n$ 個並查集樹

查詢的時候，順便維護一下（把 $l$ 到 $r$ 的 fa 都指向fa[r + 1]）

（其實用鏈表維護也可以過）

~~我好菜~~

代码#

#include<bits/stdc++.h>
#define ll long long

using namespace std; 

const int N = 1e9;
const int maxn = 1e7 + 10;
unsigned int x = 123456789, y = 362436069, z, a[maxn];
int n, q;
int fa[maxn]; 
unsigned int gen()
{
    unsigned int t;
    x ^= x << 16; x ^= x >> 5; x ^= x << 1;
    t = x; x = y; y = z; z = t ^ x ^ y;
    return z % N + 1;
}

int getfa(int u)
{
	if(fa[u] == u) return u;
	return fa[u] = getfa(fa[u]);
}

void merge(int x, int y)
{
	int xfa = getfa(x), yfa = getfa(y);
	fa[xfa] = yfa;
}

int main()
{
    scanf("%d%d%u", &n, &q, &z);
    for (int i = 1;i <= n;i++) 
        a[i] = gen(), fa[i] = i;
    fa[n + 1] = n + 1;
    unsigned ll ans = 0;
    for (int i = 1;i <= q;i++) 
    {
        int l = gen() % n + 1, r = gen() % n + 1;
        if (l > r) swap(l, r);
        unsigned ll b = 0;
        int g;
		for(int i = getfa(l);i <= r;i = g)
		{
			b += a[i];
			g = getfa(i + 1);
			merge(i, i + 1);
		}
		ans ^= b;
	
    }
    cout << ans;
}