Modify - histcat

Problem#

Given a sequence of length $n$, where the index of the $i$-th element is $i$ and the value is $a_i$.

There are $q$ operations, each time given an interval $[l,r]$, calculate the sum of the elements in that interval, and modify all element values in the interval to $0$.

You need to output the XOR sum of all operation answers.

Since $n$ and $q$ are very large, we provide another way to read input.

Given a $z$, note that its type is unsigned int, you need to call the $gen()$ function $n$ times to obtain the sequence, and then call it $2n$ times to obtain $l$ and $r$ for each operation. The specific code is as follows:

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 ...
    }
}

For $40%$ of the data, it satisfies $n, q \le 10^6$.

For $100%$ of the data, it satisfies $n, q \leq 10^7$.

Solution#

~~I won't tell you that I thought for an hour in the exam and couldn't figure it out.~~

I initially thought of using a segment tree, but considering the data range, it would definitely time out.

~~Then I didn't know how to proceed.~~

Since after querying, we can delete, we can ignore a number after querying it.

Consider using a union-find structure to maintain the numbers that can be ignored, starting with $n$ union-find trees.

During the query, we can also maintain it (make the fa from $l$ to $r$ point to fa[r + 1]).

(Actually, using a linked list to maintain it could also work.)

~~I'm so bad.~~

Code#

#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 long long 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 long long 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;
}