CF526F Pudding Monsters
- 给定一个 $n \times n$ 的棋盘，其中有 $n$ 个棋子，每行每列恰好有一个棋子。
- 求有多少个 $k \times k$ 的子棋盘中恰好有 $k$ 个棋子。
- $n \le 3 \times 10^5$。
每行每列恰好有一个棋子的棋盘，可以抽象成一个排列。 而操作也是对于一个排列的一段进行操作的。
题意可以转化为：
- 给出一个排列
- 求连续段数量，即连续的一段，且段中的元素排好序之后必须是公差为$1$的等差数列.
连续段计数
考虑如何刻画“连续的一段，且段中的元素排好序之后必须是公差为$1$的等差数列”这个条件，可以形式化的定义：
$$\operatorname{MaxVal} - \operatorname{MinVal} = (R - L)$$
即
$$f_{R}(L) = \operatorname{MaxVal} - \operatorname{MinVal} - (R - L) = 0$$
这个条件成立的基础在于，所求数列不能有重复元素，而且也保证了函数$f_x(L) \ge 0$, 查询时只需要维护最小值以及最小值的数量即可。
可以考虑枚举一个端点，比如右端点 $R$，然后查找有多少符合条件的左端点 $L$ ，用线段树维护$f_R(x)$在每个点处的函数值。
考虑当$f_x(L)$ 移动到 $f_{x + 1}(L)$ 时， 值的变化。变化的值有 $R$ , 可能变化的有$MaxVal, MinVal$。用单调栈实时维护更新后会波及哪些元素的最小值。事实上，单调栈处理的过程就是在动态维护一个后缀最小\大值数组。
这里有几个与其有相似之处的题目，但是可能做法并不一样，遇到不要想成一样的题目：
- 算术天才⑨与等差数列 (不保证序列中一定元素不重复)
- 考虑判断一个序列排好序后是否为等差数列
- 准确做法
- $\max−\min=(r−l)k$
- 相邻两数差的绝对值的 $\operatorname{gcd}$是 $k$
- 区间 $[l,r]$ 内的数不重复
- 概率性做法
- hash思想，维护 $n$ 次方和
- 考虑判断一个序列排好序后是否为等差数列
- 树上排列(ZROI) (同样不保证元素一定不重复)
- 给定一颗 $n$ 个点的树。每个点都一个正整数点权 $A_i$ ，你需要支持以下两种操作：
- 1、询问点 $x$ 和点 $y$ 之间的路径上的所有点（包括点 $x$ 和点 $y$ ）的点权是否构成一个从 $1$ 开始的排列（即若这条链长度为 $len$ ，那么问点权集合为 ${1,2,⋯,len}$ ）。
- 2、将 $A_x$ 修改为 $y$ 。
- 由于在树上难以判断某区间内的数字不重复，Hash维护n次方和。
- 给出一个没有重复元素的序列，询问某区间中的元素是否能加入小于$k$个元素使其拍好序后构成一个等差数列。
- 条件变成了 $$f_{R}(L) = \operatorname{MaxVal} - \operatorname{MinVal} - (R - L) \ge k$$
- count(ZROI)已知一个集合$S$中的最大元素为 $N$， 且这个集合中的元素可以构成一个等差数列，给出一些形如$x \in S$、$x \notin S$的限制。求最终的集合有多少种情况。
- 考虑刻画一个等差数列需要什么参数：公差，和每个元素$\bmod $ 公差的值。枚举这两个参数，依次计数即可。
（引用正睿的两道题目，不知道是不是有版权问题，如果有，会立即删除（顺便给正睿OI打个广告））。
code
{% note info CF526F Pudding Monsters %}
int n;
int A[_];
#define fir first
#define sec second
namespace SegmentTree{
const int _ = 3e6 + 100;
struct Node{
int MIN;
int sMIN;
int tar;
Node operator + (const Node & rhs) const {
Node res;
res.MIN = min(MIN, rhs.MIN);
res.sMIN = MIN == rhs.MIN ? ( sMIN + rhs.sMIN) : (MIN < rhs.MIN ? sMIN : rhs.sMIN) ;
return res;
}
}v[_];
int tot = 0;
int ch[_][2];
#define ls(o) (ch[o][0])
#define rs(o) (ch[o][1])
#define make (tot++, ch[tot][0] = ch[tot][1] = v[tot].MIN = v[tot].sMIN = 0, tot)
int Groot() { return make; }
void maintain(int o) {
v[o].MIN = min(v[ls(o)].MIN, v[rs(o)].MIN);
v[o].sMIN = v[ls(o)].MIN == v[rs(o)].MIN ? v[ls(o)].sMIN + v[rs(o)].sMIN : ( v[ls(o)].MIN < v[rs(o)].MIN ? v[ls(o)].sMIN : v[rs(o)].sMIN );
}
void tar(int o, int x) { v[o].MIN += x; v[o].tar += x; }
void pushdown(int o){
if(v[o].tar){
tar(ls(o), v[o].tar); tar(rs(o), v[o].tar);
v[o].tar = 0;
}
}
void build(int o, int L, int R){
if(L == R) { v[o].MIN = 0; v[o].sMIN = 1; return; }
int mid = (L + R) >> 1;
ls(o) = make; rs(o) = make;
build(ls(o), L, mid); build(rs(o), mid + 1, R);
maintain(o);
}
void update(int o, int nowl, int nowr, int L, int R, int x){
if(L > R) return ;
if(L <= nowl && nowr <= R) return tar(o, x);
int mid = (nowl + nowr) >> 1; pushdown(o);
if(L <= mid) update(ls(o), nowl, mid, L, R, x);
if(R > mid) update(rs(o), mid + 1, nowr, L, R, x);
maintain(o);
}
Node query(int o, int nowl, int nowr, int L, int R) {
if(L <= nowl && nowr <= R) return v[o];
int mid = (nowl + nowr) >> 1; pushdown(o);
Node Ans; Ans.MIN = INT_MAX;
if(L <= mid) Ans = Ans + query(ls(o), nowl, mid, L, R);
if(R > mid) Ans = Ans + query(rs(o), mid + 1, nowr, L, R);
return Ans;
}
int query(int o, int L, int R){
Node res = query(o, 1, n, L, R);
return res.MIN == 0 ? res.sMIN : 0;
}
} using SegmentTree::Groot; using SegmentTree::build; using SegmentTree::query; using SegmentTree::update;
namespace Mon_Stack{
int t0t = 0, t1t = 0;
pair<int, int> S0[_], S1[_];
int work(int *A, int n){
int Ans = 0;
int root = Groot();
build(root, 1, n);
S0[0].fir = S1[0].fir = 0;
for(int i = 1; i <= n; i++) {
update(root, 1, n, 1, i - 1, -1);
while(t0t != 0 && S0[t0t].sec >= A[i]) { update(root, 1, n, S0[t0t - 1].fir + 1, S0[t0t].fir, S0[t0t].sec); t0t--; }
while(t1t != 0 && S1[t1t].sec <= A[i]) { update(root, 1, n, S1[t1t - 1].fir + 1, S1[t1t].fir, -S1[t1t].sec); t1t--; }
update(root, 1, n, S0[t0t].fir + 1, i, -A[i]);
update(root, 1, n, S1[t1t].fir + 1, i, A[i]);
int t = query(root, 1, i);
Ans += t;
S0[++t0t] = make_pair(i, A[i]); S1[++t1t] = make_pair(i, A[i]);
}
return Ans;
}
} using Mon_Stack::work;
signed main(){
n = read(); for(int i = 1; i <= n; i++) { int x = read(), y = read(); A[x] = y; }
printf("%lld\n", work(A, n));
return 0;
}{% endnote %} {% note info count(ZROI) %}
#include <climits>
#include <cmath>
#include <cstring>
#include <iostream>
#include <cstdio>
#include <algorithm>
using namespace std;
#define int long long
const int MOD = 1e9 + 7;
const int _M = 2e5 + 100;
inline int read() { char c = getchar(); int sign = 1; int x = 0; while(c > '9' || c < '0') { if(c=='-')sign = -1; c = getchar(); } while(c <= '9' && c >= '0') { x *= 10; x += c - '0'; c = getchar(); } return x * sign; }
int MAX, m;
int have[_M], tht = 0;
int none[_M], tnt = 0;
int d[_M], tdt = 0;
int c[_M];//tct = tdt
bool CanBe[_M];
int ToL[_M];
int ToR[_M];
void divide(int s, int x) {
for(int i = 1; i * i <= x; i++){
if(x % i == 0) d[++tdt] = i, c[tdt] = s % i;
if(i * i != x) d[++tdt] = x / i, c[tdt] = s % d[tdt];
}
for(int i = 1; i <= tdt; i++) CanBe[i] = true;
}
signed main(){
int t;
MAX = read(), m = read();
for(int i = 1; i <= m; i++){
int type = read();
if(type == 1) have[++tht] = read();
else none[++tnt] = read();
}
sort(have + 1, have + 1 + tht); sort(none + 1, none + 1 + tnt);
int maxd = INT_MAX, Sta;
for(int i = 2; i <= tht; i++) {
if(maxd > have[i] - have[i - 1]){
maxd = have[i] - have[i - 1];
Sta = have[i - 1];
}
}
divide(Sta, maxd);
/* 公差 及 特征 检查 */
for(int i = 1; i <= tht; i++){
for(int j = 1; j <= tdt; j++){
if(!CanBe[j]) continue;
if(have[i] % d[j] != c[j]) CanBe[j] = false;
}
}
for(int i = 2; i <= tht; i++){
int D = have[i] - have[i - 1];
for(int j = 1; j <= tdt; j++){
if(!CanBe[j]) continue;
if(D % d[j] != 0) CanBe[j] = false;
}
}
t = 0;
for(int i = 1; i <= tdt; i++){
if(!CanBe[i]) continue;
d[++t] = d[i];
c[ t] = c[i];
CanBe[t] = true;
} tdt = t;
/* 公差 及 特征 检查 完成*/
for(int i = 1; i <= tdt; i++) {
if(CanBe[i]) {
ToL[i] = (c[i] == 0 ? d[i] : c[i]) - 1;
int t = MAX % d[i];
if(t == c[i]) ToR[i] = MAX + 1;
if(t > c[i]) ToR[i] = MAX - (t - c[i]) + 1;
if(t < c[i]) ToR[i] = MAX - d[i] + (c[i] - t) + 1;
}
}
t = 0;
for(int i = 1; i <= tdt; i++){
if(!CanBe[i]) continue;
d[++t] = d[i];
c[ t] = c[i];
CanBe[t] = true;
} tdt = t;
int MINS = have[1], MAXE = have[tht];
for(int i = 1; i <= tnt; i++){
int now = none[i];
for(int j = 1; j <= tdt; j++){
if(!CanBe[j]) continue;
if(now % d[j] == c[j]){
if(now < MINS)
ToL[j] = max(ToL[j], now);
else if(now > MAXE)
ToR[j] = min(ToR[j], now);
else CanBe[j] = false;
}
}
}
for(int i = 1; i <= tdt; i++) if(ToL[i] > MINS || ToR[i] < MAXE) CanBe[i] = false; else ToL[i]++, ToR[i] --;
/* 非法数字存在性检查 */
int ans = 0;
for(int i = 1; i <= tdt; i++){
if(!CanBe[i]) continue;
int k = ( (MINS - ToL[i]) / d[i] + 1) * ( (ToR[i] - MAXE) / d[i] + 1) % MOD; // TODO;
ans = (ans + k) % MOD;
}
printf("%lld", ans);
return 0;
}{% endnote %} {% note info A.20联赛集训day3 树上排列(维护15次方和hash) %}
#include <climits>
#include <cstring>
#include <cmath>
#include <iostream>
#include <algorithm>
#include <vector>
inline int read() { char c = getchar(); int sign = 1; int x = 0; while(c > '9' || c < '0') { if(c=='-')sign = -1; c = getchar(); } while(c <= '9' && c >= '0') { x *= 10; x += c - '0'; c = getchar(); } return x * sign; }
using namespace std;
const int _ = 6e5 + 100;
const int base = 15;
const int MOD = 1020031005;
int SS[_];
int pow(int a, int b = base){ int ans = 1; while(b){ if(b & 1) ans = (ans *1ll* a) % MOD; a = (a *1ll* a) % MOD; b >>= 1; } return ans; }
int head[_];
int NodeVal[_];
struct edges{
int node;
int nxt;
}edge[_];
int tot = 0;
void add(int u, int v){
tot++;
edge[tot].node = v;
edge[tot].nxt = head[u];
head[u] = tot;
}
int n, q;
int dep[_], fa[_], dfn[_], rnk[_], top[_], son[_], si[_], dfc = 0;
void dfs0(int now, int f, int dp){
int &S = si[now] = 1; int &Mid = son[now] = 0; fa[now] = f; dep[now] = dp;
for(int i = head[now]; i ; i = edge[i].nxt){
int ex = edge[i].node; if(ex == f) continue;
dfs0(ex, now, dp + 1); S += si[ex];
if(si[ex] > si[Mid]) Mid = ex;
} if(!Mid) Mid = 0;
}
void dfs1(int now, int f, int tp){
dfn[now] = ++dfc; rnk[dfc] = now;
top[now] = tp;
if(son[now]) dfs1(son[now], now, tp);
for(int i = head[now]; i ; i = edge[i].nxt){
int ex = edge[i].node; if(ex == f || ex == son[now]) continue;
dfs1(ex, now, ex);
}
}
void clear(){
memset(head, 0, sizeof(head));
dfn[0] = rnk[0] = si[0] = top[0] = fa[0] = son[0] = 0;
tot = 0;
dfc = 0;
}
namespace SegmentTree{
const int _ = 3e6 + 100;
int tot = 0;
int ch[_][2];
int v[_];
#define make (tot++, ch[tot][0] = ch[tot][1] = v[tot] = 0, tot);
#define ls(x) (ch[x][0])
#define rs(x) (ch[x][1])
#define maintain(o) (v[o] = (v[ls(o)] +0ll+ v[rs(o)]) % MOD )
void init_s() { tot = 0; }
int Groot(){ return make; }
void build(int o, int L, int R){
if(L == R) return (void)(v[o] = pow(NodeVal[rnk[L]]));
int mid = (L + R) >> 1;
ls(o) = make; rs(o) = make;
build(ls(o), L, mid); build(rs(o), mid + 1, R);
maintain(o);
}
void update(int o, int nowl, int nowr, int p, int x){
if(nowl == nowr) return (void)(v[o] = pow(x));
int mid = (nowl + nowr) >> 1;
if(p <= mid) update(ls(o), nowl, mid, p, x);
if(p > mid) update(rs(o), mid + 1, nowr, p, x);
maintain(o);
}
int query(int o, int nowl, int nowr, int L, int R){
if(L > R) return 0;
if(L <= nowl && nowr <= R) return v[o];
int mid = (nowl + nowr) >> 1;
int ans = 0;
if(L <= mid) ans = (ans +0ll+ query(ls(o), nowl, mid, L, R)) % MOD;
if(R > mid) ans = (ans +0ll+ query(rs(o), mid + 1, nowr, L, R)) % MOD;
return ans;
}
} using SegmentTree::Groot; using SegmentTree::init_s; using SegmentTree::build; using SegmentTree::update; using SegmentTree::query;
int root = 0;
int LCA;
int QueryOnPath(int x, int y){
int ans = 0;
while(top[x] != top[y]){
if(dep[top[x]] > dep[top[y]]) swap(x, y);
ans = (ans +0ll+ query(root, 1, n, dfn[top[y]], dfn[y])) % MOD;
y = fa[top[y]];
}
if(dep[x] < dep[y]) swap(x, y); LCA = y;
ans = (ans +0ll+ query(root, 1, n, dfn[y], dfn[x])) % MOD;
return ans;
}
void doit(){
clear();
n = read(), q = read();
for(int i = 1; i <= n; i++) NodeVal[i] = read();
for(int i = 1; i < n; i++){ int u = read(), v = read(); add(u, v); add(v, u); }
dfs0(1, 1, 1);
dfs1(1, 1, 1);
init_s(); root = Groot();
build(root, 1, n);
while(q--){
int opt = read(), x = read(), y = read();
if(opt == 1){
int r = QueryOnPath(x, y);
int Len = dep[x] + dep[y] - (dep[LCA] << 1) + 1;
puts(SS[Len] == r ? "Yes" : "No");
} else{
update(root, 1, n, dfn[x], y);
}
}
}
int main(){
for(int i = 1; i <= 3e5; i++) SS[i] = ( SS[i - 1] +0ll+ pow(i) ) % MOD;
int T = read();
while(T--) doit();
return 0;
}{% endnote %}
