XTCPC2019 F.Neko and sequence
题目链接
http://acm.hdu.edu.cn/showproblem.php?pid=6539
题目大意
给你一个长度为 $n$ 的括号序列，定义 $f(i, d)$ 为从 $i$ 出发，如果当前位置是 $’)’$ ，那么就向右走 $k$ ，否则向左走 $k$ ，这样行走 $d$ 次。一共 $q$ 次询问，每次给你一组 $l, r, d$ ，询问 $\sum\limits_{i=l}^r{f(i, d)}$
题目分析
这种括号序列显然无论怎么走，走到一定时候之后就会出现循环节。那么一共可能出现两种循环节：
-
走到最后两个不同方向的点之间互相走。
-
一整串相同方向的点构成循环节。
先来考虑第一种，那么显然如果足够大了那么就是每个点只分奇数和偶数两种情况，显然用树状数组可以维护。
那么剩下需要处理的就是不够大的部分。显然对于每个点如果没有进入第一种请况的循环节的话一定是向同一个方向走的。那么其实是和第二种情况是类似的可以一块儿处理。
这时对于每个点的答案就是 $(i + kd) \mod n$ 或 $(i – kd) \mod n$，这不是太好计算。但是如果令 $z = kd \mod n$ 的话，那么其实 $kd$ 换为 $z$ 的话并不影响答案，但是变化量被限制在了 $[0, n)$ 。那么只需要分类讨论一下，计算结果对 $n$ 取模之前在 $[0, n)$ 之间的和不在的可以分开处理，那么只需要使用树状数组就可以快速计算出不同区间的贡献。
按照时间排序来处理上述内容和询问即可得到答案。
代码
#include <bits/stdc++.h>
using namespace std;
const int maxn = 2e5 + 5;
int n, q, k;
char str[maxn];
bool vis[maxn];
struct ex {
int l, r, d, n;
};
ex opt[maxn];
int dis[maxn];
int f[maxn][2];
long long ans[maxn];
vector <pair <int, int> > vec;
struct bt {
long long tree[maxn];
int lowbit(int x){
return x & -x;
}
long long sum(long long p){
long long ret = 0;
p++;
while(p){
ret += tree[p];
p -= lowbit(p);
}
return ret;
}
int update(int p, long long x){
p++;
while(p <= n){
tree[p] += x;
p += lowbit(p);
}
return 0;
}
long long query(int l, int r){
return sum(r) - sum(l - 1);
}
int init(){
memset(tree, 0, sizeof(tree));
return 0;
}
} ta[4], tb[2];
bool cmp(ex x, ex y){
return x.d < y.d;
}
int go(int x){
if(str[x] == ')')return (x + k) % n;
return (x - k + n) % n;
}
int dfs(int x){
int y = go(x);
vis[x] = true;
if(go(y) == x){
dis[x] = 0;
f[x][0] = x;
f[x][1] = y;
}else{
if(!vis[y])dfs(y);
dis[x] = dis[y] + 1;
f[x][0] = f[y][1];
f[x][1] = f[y][0];
}
return 0;
}
int main(){
int i, j;
int tt = 0;
while(~scanf("%d%d%d", &n, &q, &k)){
for(i=0;i<n;i++){
scanf(" %c", &str[i]);
vis[i] = false;
f[i][0] = f[i][1] = 0;
}
for(i=1;i<=q;i++){
scanf("%d%d%d", &opt[i].l, &opt[i].r, &opt[i].d);
opt[i].n = i;
}
for(i=0;i<n;i++){
if(!vis[i])dfs(i);
}
sort(opt + 1, opt + q + 1, cmp);
ta[0].init(), ta[1].init(), ta[2].init(), ta[3].init(), tb[0].init(), tb[1].init();
vec.clear();
for(i=0;i<n;i++){
if(dis[i] == 0 and (f[i][0] or f[i][1])){
tb[0].update(i, f[i][0]);
tb[1].update(i, f[i][1]);
}else{
if(str[i] == ')'){
ta[0].update(i, i);
ta[1].update(i, 1);
}else{
ta[2].update(i, i);
ta[3].update(i, 1);
}
if(f[i][0] or f[i][1])vec.push_back(make_pair(dis[i], i));
}
}
sort(vec.begin(), vec.end());
for(i=1,j=0;i<=q;i++){
while(j < vec.size() and vec[j].first < opt[i].d){
tb[0].update(vec[j].second, f[vec[j].second][0]);
tb[1].update(vec[j].second, f[vec[j].second][1]);
if(str[vec[j].second] == ')'){
ta[0].update(vec[j].second, -vec[j].second);
ta[1].update(vec[j].second, -1);
}else{
ta[2].update(vec[j].second, -vec[j].second);
ta[3].update(vec[j].second, -1);
}
j++;
}
int z = (1ll * k * opt[i].d) % n;
int l = opt[i].l, r = opt[i].r;
ans[opt[i].n] = 0;
if(l < n - z){
ans[opt[i].n] += ta[0].query(l, min(n - z - 1, r)) + 1ll * ta[1].query(l, min(n - z - 1, r)) * z;
}
if(r >= n - z){
ans[opt[i].n] += ta[0].query(max(l, n - z), r) + 1ll * ta[1].query(max(l, n - z), r) * (z - n);
}
if(l < z){
ans[opt[i].n] += ta[2].query(l, min(r, z - 1)) + 1ll * ta[3].query(l, min(r, z - 1)) * (n - z);
}
if(r >= z){
ans[opt[i].n] += ta[2].query(max(l, z), r) - 1ll * ta[3].query(max(l, z), r) * z;
}
ans[opt[i].n] += tb[opt[i].d & 1].query(l, r);
}
for(i=1;i<=q;i++){
printf("%lld\n", ans[i]);
}
}
return 0;
}