目录
写在前面
寒假集训期间杂题选记。
CF1288E
知识点：数据结构，乱搞
小清新数据结构。
显然 \(i\) 最靠上的出现位置不是 1 就是 \(i\)；\(i\) 最靠下的位置一定出现在 \(i\) 即将被扔到顶上前或者所有操作结束之后，且此时 \(i\) 的位置即为在它之上的元素的个数。
发现比较难处理的是当某个位置被扔到顶上之后其他元素的后移，但是发现其实并不需要真的显式地将这些元素后移，仅需要维护相对的前后关系，并支持一个前缀的查询即可。
考虑维护一个长度为 \(m+n\) 的 01 序列，1 表示该位置有元素。初始时位置 \(m + 1\sim n\) 为 1；另外维护 \(\operatorname{pos}_i\) 表示元素 \(i\) 所在位置。第 \(j\) 次操作将 \(i\) 移动到顶部时，查询 \(1\sim \operatorname{pos}_i\) 之和即为 \(i\) 此时的排名，然后 \(\operatorname{pos}_i\) 置 0，将位置 \(m-j+1\) 置 1，然后更新 \(\operatorname{pos}_i = m-j+1\) 即可。
注意还需要在所有操作进行完后对所有元素求一次排名。
总复杂度 \(O((n + m)\log (n + m))\) 级别。
//
/*
By:Luckyblock
*/
#include <bits/stdc++.h>
#define LL long long
const int kN = 3e5 + 10;
//=============================================================
int n, m, pos[kN];
int ans1[kN], ans2[kN];
//=============================================================
inline int read() {
int f = 1, w = 0; char ch = getchar();
for (; !isdigit(ch); ch = getchar()) if (ch == '-') f = -1;
for (; isdigit(ch); ch = getchar()) w = (w << 3) + (w << 1) + (ch ^ '0');
return f * w;
}
namespace Bit {
#define lowbit(x) ((x)&(-x))
int lim, t[kN << 1];
void Init(int n_) {
lim = n_;
}
void Insert(int pos_, int val_) {
for (int i = pos_; i <= lim; i += lowbit(i)) {
t[i] += val_;
}
}
int Sum(int pos_) {
int ret = 0;
for (int i = pos_; i; i -= lowbit(i)) {
ret += t[i];
}
return ret;
}
int Query(int l_, int r_) {
return Sum(r_) - Sum(l_ - 1);
}
#undef lowbit
}
//=============================================================
int main() {
//freopen("1.txt", "r", stdin);
n = read(), m = read();
Bit::Init(n + m);
for (int i = 1; i <= n; ++ i) {
pos[i] = m + i;
ans1[i] = ans2[i] = i;
Bit::Insert(pos[i], 1);
}
for (int i = m; i; -- i) {
int x = read();
ans1[x] = 1;
ans2[x] = std::max(ans2[x], Bit::Sum(pos[x]));
Bit::Insert(pos[x], -1);
pos[x] = i;
Bit::Insert(pos[x], 1);
}
for (int i = 1; i <= n; ++ i) {
ans2[i] = std::max(ans2[i], Bit::Sum(pos[i]));
}
for (int i = 1; i <= n; ++ i) {
printf("%d %d\n", ans1[i], ans2[i]);
}
return 0;
}
P3538 [POI2012] OKR-A Horrible Poem
知识点：哈希，二分，枚举
一眼题，但是卡常。
首先 \(5\times 10^5\) 内的数至多只有 100 多个因子，可以考虑对每个询问都大力枚举区间长度的所有因子 \(d\)，然后检查 \(d\) 是否可以作为循环节；然后是典中典结论，若 \(s[1: |s| - d] = s[d + 1: |s|]\)，则 \(s[1:d]\) 是 \(s\) 的循环节，哈希判断即可。
这题卡因数分解呃呃，改成线性筛质因数分解 + dfs 求因数还过不去，懒得改了。
90pts 代码：
//
/*
By:Luckyblock
*/
#include <bits/stdc++.h>
#define LL long long
const int kN = 5e5 + 10;
const LL c1 = 1145141;
const LL p1 = 998244353;
//=============================================================
int n, q;
char s[kN];
int pnum, p[kN], minp[kN];
bool vis[kN];
std::vector <int> d;
LL pw1[kN], h1[kN];
int ans;
//=============================================================
inline int read() {
int f = 1, w = 0; char ch = getchar();
for (; !isdigit(ch); ch = getchar()) if (ch == '-') f = -1;
for (; isdigit(ch); ch = getchar()) w = (w << 3) + (w << 1) + (ch ^ '0');
return f * w;
}
void Init() {
for (int i = 2; i <= n; ++ i) {
if (! vis[i]) p[++ pnum] = i, minp[i] = i;
for (int j = 1; j <= pnum; ++ j) {
if (i * p[j] > n) break;
vis[i * p[j]] = true;
minp[i * p[j]] = p[j];
if (i % p[j] == 0) break;
}
}
pw1[0] = 1;
for (int i = 1; i <= n; ++ i) {
pw1[i] = pw1[i - 1] * c1 % p1;
h1[i] = (c1 * h1[i - 1] % p1 + s[i]) % p1;
}
}
LL hash(int l_, int r_) {
LL ret1 = (h1[r_] - pw1[r_ - l_ + 1] * h1[l_ - 1] % p1 + p1) % p1;
return ret1;
}
bool check(int l_, int r_, int x_) {
LL ret1 = hash(l_, r_ - x_);
LL ret2 = hash(l_ + x_, r_);
return ret1 == ret2;
}
void Dfs(int l_, int r_, int len_, int i_, int sum_) {
if (i_ >= (int) d.size()) {
if (check(l_, r_, sum_)) ans = sum_;
return ;
}
while (sum_ < len_ && len_ % sum_ == 0 && sum_ < ans) {
Dfs(l_, r_, len_, i_ + 1, sum_);
if (1ll * sum_ * d[i_] > len_) break;
sum_ *= d[i_];
}
return ;
}
int query(int l_, int r_) {
int now = ans = r_ - l_ + 1;
d.clear();
while (now != 1) {
int nowp = minp[now];
d.push_back(nowp);
while (now % nowp == 0) now /= nowp;
}
std::reverse(d.begin(), d.end());
Dfs(l_, r_, r_ - l_ + 1, 0, 1);
return ans;
}
//=============================================================
int main() {
// freopen("1.txt", "r", stdin);
n = read();
scanf("%s", s + 1);
Init();
q = read();
while (q --) {
int l_ = read(), r_ = read();
printf("%d\n", query(l_, r_));
}
return 0;
}
/*
8
aaabcabc
1
3 8
*/