[LOJ][HAOI2017]供给侧改革

LOJ][HAOI2017]供给侧改革"/>

[LOJ][HAOI2017]供给侧改革

链接

神奇的题目

对于一个询问 \([L , R]\) , 区间 \([i , R]\) 肯定是随着 \(i\) 的增大而不递增的 ，这就给我们提供了维护区间长度的思路。
而且该 \(01\) 序列中对于一对后缀公共前缀长度稍微长一点都是概率极低的 ， 所以我们假设一个不大的长度 \(lim\) 表示所有最长公共前缀的长度上界。
结合第一个性质我们可以只维护 \(lim\) 个区间的长度。
将询问按照 \(r\) 从小到大排序 ， 扫到 \(r\) 时计算这个询问就行了。
长度具体的维护方法是建立一颗 \(Trie\) , 枚举到后缀 \(i\) 时，将 \([i , i + lim)\) 加入到Trie , 并且对于每个 \(Trie\) 中的结点维护最后一次访问这个结点的后缀，下一次扫到这个结点时可以维护最小区间的长度，具体方法看代码。

#include<iostream>
#include<algorithm>
#include<cstring>
#include<cmath>
#include<map>
#include<stack>
#include<queue>
#include<set>
#include<vector>
#include<cstdio>
#define lson k << 1
#define rson k << 1 | 1using namespace std;
typedef long long ll;
const int N = 100005 , Mod = 998244353 , G = 3 , INF = 0x3f3f3f3f;
double Pi = acos(-1);struct Virt{double x , y;Virt(double _x = 0.0 , double _y = 0.0):x(_x) , y(_y){}
};Virt operator + (Virt x , Virt y){return Virt(x.x + y.x , x.y + y.y);}
Virt operator - (Virt x , Virt y){return Virt(x.x - y.x , x.y - y.y);}
Virt operator * (Virt x , Virt y){return Virt(x.x * y.x - x.y * y.y , x.x * y.y + x.y * y.x);}int read(){int x = 0 , f = 1; char ch = getchar();while(ch < '0' || ch > '9'){if(ch == '-') f = -1 ; ch = getchar();}while(ch >= '0' && ch <= '9'){x = x * 10 + ch - '0'; ch = getchar();}return x * f;
}int cnt , n , Q , ch[N * 40][2] , dep[105] , las[N * 40] , lim;
ll ans[N];
char s[N];struct query{int l , r , pos;
}q[N];bool comp(query x , query y){return x.r < y.r;}void insert(int x){int p = 0 , c;for(int i = 0 ; i + x <= n && i + 1 <= lim ; i++){c = s[i + x] - '0';if(!ch[p][c]) ch[p][c] = ++cnt;else dep[i + 1] = max(dep[i + 1] , las[ch[p][c]]);las[ch[p][c]] = x;p = ch[p][c];}
}int main(){int l , r;n = read(); Q = read();scanf("%s",s + 1);for(int i = 1 ; i <= Q ; i++){l = read(); r = read();q[i].l = l; q[i].r = r; q[i].pos = i;}sort(q + 1 , q + 1 + Q , comp);lim = min(n , 40);int cur = 1;for(int i = 1 ; i <= n ; i++){insert(i);while(q[cur].r == i && cur <= Q){for(int j = 1 ; j <= lim ; j++){if(dep[j] >= q[cur].l){ans[q[cur].pos] += 1ll * (dep[j] - max(q[cur].l - 1 , dep[j + 1])) * j;}else break;             }cur++;}}for(int i = 1 ; i <= Q ; i++)   printf("%lld\n",ans[i]);
}

转载于:.html