#include<bits/stdc++.h>
using namespace std;
#define X first
#define Y second
#define sz(a) (int)a.size()
#define ll long long
const int N = 4e5 + 100;
const int T = 20;
int n, m, t;
ll mod;
ll a[N];
int lca[N][T];
int up[N];
int vals[N];
int H[N];
int idx[N];
vector <pair <int, int> > vec[N];
vector <int> g[N];
int it = 2e5;
struct node{
node* left;
node* right;
int _sz;
node(){};
};
void dfs(int v)
{
for(auto to : g[v])
{
H[to] = H[v] + 1;
dfs(to);
}
}
node* mass[N];
int go_to(node* v, int l, int r, int d)
{
if(l == r)
{
return l;
}
if(v -> left -> _sz <= d)
{
return go_to(v -> right, (r + l) / 2 + 1, r, d - v -> left -> _sz);
}
return go_to(v -> left, l, (r + l) / 2, d);
}
void go_to1(node* pr, node *&v, int l, int r, int k)
{
v -> _sz = pr -> _sz;
v -> _sz--;
if(l == r)
{
return;
}
if(k <= (r + l) / 2)
{
v -> left = new node();
v -> right = pr -> right;
go_to1(pr -> left, v -> left, l, (r + l) / 2, k);
}
else
{
v -> left = pr -> left;
v -> right = new node();
go_to1(pr -> right, v -> right, (r + l) / 2 + 1, r, k);
}
}
pair <int, int> funct(ll a)
{
int l = -1, r = n;
while(r - l > 1)
{
ll midd = (r + l) / 2;
if((midd + 2) * (midd + 1) / 2 <= a)
{
l = midd;
}
else
{
r = midd;
}
}
return {l + 1, a - 1LL * (l + 2) * (l + 1) / 2};
}
int go_to2(node* v, int l, int r, int x)
{
if(!v -> _sz)
{
return -1;
}
if(l > x)
{
return -1;
}
if(l == r)
{
return l;
}
if(r <= x)
{
if(v -> right -> _sz)
{
return go_to2(v -> right, (r + l) / 2 + 1, r, x);
}
return go_to2(v -> left, l, (r + l) / 2, x);
}
int t2 = go_to2(v -> right, (r + l) / 2 + 1, r, x);
if(t2 != -1)
{
return t2;
}
int t1 = go_to2(v -> left, l, (r + l) / 2, x);
return t1;
}
int coun(node* v, int l, int r, int x)
{
if(x < l)
{
return 0;
}
if(r <= x)
{
return v -> _sz;
}
return coun(v -> left, l, (r + l) / 2, x) + coun(v -> right, (r + l) / 2 + 1, r, x);
}
ll query(ll a, ll b)
{
pair <int, int> t = funct(a);
pair <int, int> t1 = funct(b);
t.Y = go_to(mass[t.X], 0, n, t.Y);
t1.Y = go_to(mass[t1.X], 0, n, t1.Y);
if(t.X > t1.X)
{
swap(t, t1);
}
t.Y = go_to2(mass[t.X], 0, n, t.Y);
t1.Y = go_to2(mass[t.X], 0, n, t1.Y);
//cout << t.X << " " << t.Y << " " << t1.X << " " << t1.Y << "\n";
int f1 = lower_bound(vec[t.Y].begin(), vec[t.Y].end(), make_pair(t.X, 0)) - vec[t.Y].begin();
t.Y = vec[t.Y][f1].Y;
f1 = lower_bound(vec[t1.Y].begin(), vec[t1.Y].end(), make_pair(t.X, 0)) - vec[t1.Y].begin();
t1.Y = vec[t1.Y][f1].Y;
if(t.Y > t1.Y)
{
swap(t.Y, t1.Y);
}
// cout << t.X << " " << t.Y << " " << t1.X << " " << t1.Y << "\n";
if(t.Y == t1.Y)
{
t.Y = coun(mass[t.X], 0, n, idx[t.Y] - 1);
return t.Y + 1 + 1LL * t.X * (t.X + 1) / 2;
}
if(H[t.Y] > H[t1.Y])
{
swap(t, t1);
}
int len = H[t1.Y] - H[t.Y];
for(int j = T - 1; j >= 0; j--)
{
if((1 << j ) <= len)
{
len -= (1 << j);
t1.Y = lca[t1.Y][j];
}
}
// cout << t.Y << " " << t1.Y << "\n";
for(int i = T - 1; i >= 0; i--)
{
if(lca[t1.Y][i] == lca[t.Y][i])
{
continue;
}
t1.Y = lca[t1.Y][i];
t.Y = lca[t.Y][i];
}
t1.Y = lca[t1.Y][0];
//cout << t1.Y << "\n";
t.X = up[t1.Y];
// cout << t.X << "\n";
t.Y = coun(mass[t.X], 0, n, idx[t1.Y] - 1);
return t.Y + 1 + 1LL * (t.X) * (t.X + 1) / 2;
}
void build(node* &v, int l, int r)
{
v -> _sz = r - l + 1;
if(l == r)
{
return;
}
v -> left = new node();
v -> right = new node();
build(v -> left, l, (r + l) / 2);
build(v -> right, (r + l) / 2 + 1, r);
}
signed main()
{
// ifstream cin("input1.txt.4c");
ios_base::sync_with_stdio(0);
cin.tie(0);
cout.tie(0);
cin >> n >> m >> t;
// cout << n << "\n";
mod = 1LL * (n + 1) * (n + 2) / 2;
for(int i = 0; i < n; i++)
{
cin >> a[i];
}
mass[n] = new node();
build(mass[n], 0, n);
//cout << "A\n";
lca[0][0] = 0;
up[0] = -1;
for(int i = 0; i <= n; i++)
{
vals[i] = i;
idx[i] = i;
up[i] = n;
vec[i].push_back({n, i});
}
for(int i = n - 1; i >= 0; i--)
{
a[i] -= 1LL * i * (i + 1) / 2;
int u1 =go_to(mass[i + 1], 0, n, a[i] - 1);
int u = go_to(mass[i + 1], 0, n, a[i]);
vec[u1].push_back({i, it + 1});
idx[it + 1] = u1;
g[it + 1].push_back(vals[u]);
g[it + 1].push_back(vals[u1]);
lca[vals[u]][0] = it + 1;
lca[vals[u1]][0] = it + 1;
up[it + 1] = i;
vals[u1] = ++it;
mass[i] = new node();
go_to1(mass[i + 1], mass[i], 0, n, u);
}
for(int i = 0; i <= n; i++)
{
sort(vec[i].begin(), vec[i].end());
}
dfs(it);
for(int j = 1; j < T; j++)
{
for(int i = 0; i <= n * 2; i++)
{
lca[i][j] = lca[lca[i][j - 1]][j - 1];
}
}
ll z = 0;
for(int i = 0; i < m; i++)
{
ll a, b;
cin >> a >> b;
a = (a - 1 + 1LL * t * z) % mod;
b = (b - 1 + 1LL * t * z) % mod;
cout << (z = query(a, b)) << "\n";
}
return 0;
}
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
697 ms |
202304 KB |
Output is correct |
| 2 |
Incorrect |
46 ms |
34672 KB |
Output isn't correct |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
697 ms |
202304 KB |
Output is correct |
| 2 |
Incorrect |
46 ms |
34672 KB |
Output isn't correct |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
697 ms |
202304 KB |
Output is correct |
| 2 |
Incorrect |
46 ms |
34672 KB |
Output isn't correct |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1997 ms |
202796 KB |
Output is correct |
| 2 |
Incorrect |
1428 ms |
115272 KB |
Output isn't correct |
| 3 |
Halted |
0 ms |
0 KB |
- |
