D - Linear Probing- 并查集

D - Linear Probing Editorial

 / 

Time Limit: 4 sec / Memory Limit: 1024 MB

Score : 400400 points

Problem Statement

There is a sequence A = (A_0, A_1, \dots, A_{N - 1})A=(A0​,A1​,…,AN−1​) with N = 2^{20}N=220 terms. Initially, every term is -1−1.

Process QQ queries in order. The ii-th query (1 \leq i \leq Q)(1≤i≤Q) is described by an integer t_iti​ such that t_i = 1ti​=1 or t_i = 2ti​=2, and another integer x_ixi​, as follows.

• If t_i = 1ti​=1, do the following in order.
  1. Define an integer hh as h = x_ih=xi​.
  2. While A_{h \bmod N} \neq -1AhmodN​=−1, keep adding 11 to hh. We can prove that this process ends after finite iterations under the Constraints of this problem.
  3. Replace the value of A_{h \bmod N}AhmodN​ with x_ixi​.
• If t_i = 2ti​=2, print the value of A_{x_i \bmod N}Axi​modN​ at that time.

Here, for integers aa and bb, a \bmod bamodb denotes the remainder when aa is divided by bb.

Constraints

• 1 \leq Q \leq 2 \times 10^51≤Q≤2×105
• t_i \in \{ 1, 2 \} \, (1 \leq i \leq Q)ti​∈{1,2}(1≤i≤Q)
• 0 \leq x_i \leq 10^{18} \, (1 \leq i \leq Q)0≤xi​≤1018(1≤i≤Q)
• There is at least one ii (1 \leq i \leq Q)(1≤i≤Q) such that t_i = 2ti​=2.
• All values in input are integers.

Input

Input is given from Standard Input in the following format:

QQ
t_1t1​ x_1x1​
\vdots⋮
t_{Q}tQ​ x_{Q}xQ​

Output

并查集概念详解

pptx 0星 超过10%的资源 1.12MB

下载

For each query with t_i = 2ti​=2, print the response in one line. It is guaranteed that there is at least one such query.

Sample Input 1 Copy

Copy

4
1 1048577
1 1
2 2097153
2 3

Sample Output 1 Copy

Copy

1048577
-1

We have x_1 \bmod N = 1x1​modN=1, so the first query sets A_1 = 1048577A1​=1048577.

In the second query, initially we have h = x_2h=x2​, for which A_{h \bmod N} = A_{1} \neq -1AhmodN​=A1​=−1, so we add 11 to hh. Now we have A_{h \bmod N} = A_{2} = -1AhmodN​=A2​=−1, so this query sets A_2 = 1A2​=1.

In the third query, we print A_{x_3 \bmod N} = A_{1} = 1048577Ax3​modN​=A1​=1048577.

In the fourth query, we print A_{x_4 \bmod N} = A_{3} = -1Ax4​modN​=A3​=−1.

Note that, in this problem, N = 2^{20} = 1048576N=220=1048576 is a constant and not given in input.

=========================================================================非常巧妙的一个题目，直接循环外加优化的话只会TLE一个点，本题正解是并查集，每当修改一个位置，就把这个位置的父亲节点和父亲节点+1位置合并，注意合并顺序，这样我们就完美的定位了下一个位置，十分精巧

# include
# include
# include
# include
# include
# include
# include
# pragma optimize(2)
# define mod 1048576
using namespace std;
 
typedef long long int ll;
 
int f[(1<<20)+10];
 
ll ans[(1<<20)+10];
 
bool book[1048576+10];
 
ll getf(int x)
{
    if(x==f[x])
        return x;
    else
    {
        f[x]=getf(f[x]);
        return f[x];
 
    }
}
 
void hebing(int x,int y)
{
    int t1=getf(x);
    int t2=getf(y);
 
    if(t1!=t2)
        f[t1]=t2;
 
 
}
int main ()
{
 
    for(int i=0; i<(1<<20); i++)
    {
        f[i]=i;
 
    }
 
    int t;
 
    cin>>t;
 
    while(t--)
    {
        ll x,y;
 
        scanf("%lld%lld",&x,&y);
 
        if(x==1)
        {
 
            ll pre=y;
 
            y%=1048576;
 
            ll now=getf(y);
 
            ans[now]=pre;
 
            book[now]=1;
 
            hebing(now,(now+1)%1048576);
 
        }
        else
        {
            ll now=y%1048576;
 
 
            if(!book[now])
            {
                cout<<-1<<'\n';
            }
            else
            {
 
 
                cout<'\n';
            }
 
        }
    }
 
 
    return 0;
 
}