析合树是你的谎言

析合树是你的谎言

题目

题目背景
最权威的题目难度分类：

public long long DifficultyRate(Problem task){if(Principal.canSolve(task) == false)return Long.MAX_VALUE; // Principal {aka XYX}if(DDG.canSolve(task) == false)return Integer.MAX_VALUE; // DDG {aka *human*}if(OneInDark.canSolve(task) == true)return Integer.MIN_VALUE; // OID {aka Garbage}// following are commercial secrets
}

题目描述
上次 p r i n c i p a l rm principal principal 听说 l c a lca lca 先他一步搞出了析合树，心中非常不爽，于是出了这样一道题：

台历上每一天排成一个 n × m ntimes m n×m 的矩阵，每一天的格子中写有一个数字 w i , j w_{i,j} wi,j​，表示 S i s t e r color{black}Scolor{red}{ister} Sister 今天的 i n c o m e p e r p e r s o n rm income;per;person incomeperperson 。而 O n e I n D a r k sf OneInDark OneInDark 准备在一个子矩形对应的日子中消费。如果这几天中花费的价格构成的集合是连续自然数， O n e I n D a r k sf OneInDark OneInDark 就会在这些日子里放纵自己……

那么，假设每一个可行的子矩形都被选中了，放纵天数总和是多少？

数据范围与提示
1 ⩽ w i , j ⩽ n × m ⩽ 2 × 1 0 5 1leqslant w_{i,j}leqslant ntimes mleqslant 2times 10^5 1⩽wi,j​⩽n×m⩽2×105，保证 w i , j w_{i,j} wi,j​ 两两不同。

思路

最大的陷阱就是析合树。

在一维问题上，枚举序列的区间，和枚举值域的区间，二者是等价的。可是在二维问题上，明显枚举一个子矩形的难度就变高了……

考虑 枚举值域区间，问题转化为判断 特殊点是否构成一个大矩形。拓展一维问题的做法？考虑最小的能包含所有特殊点的子矩形，即 ( min ⁡ x , min ⁡ y ) (min x,min y) (minx,miny) 和 ( max ⁡ x , max ⁡ y ) (max x,max y) (maxx,maxy) 撑起的子矩形，大小是否为特殊点数量。

但是 x x x 和 y y y 是乘起来的！我们就需要解决这样一个问题：

• 有两个序列 a 1 , a 2 , … , a n a_1,a_2,dots,a_n a1​,a2​,…,an​ 和 b 1 , b 2 , … , b n b_1,b_2,dots,b_n b1​,b2​,…,bn​ 。
• 每次可以对其中一个序列进行区间加（保证加一个正数）。
• 保证 a l b l ⩾ r − l + 1 a_lb_lgeqslant r-l+1 al​bl​⩾r−l+1，所以求 a l b l + l a_lb_l+l al​bl​+l 的最小值 r + 1 r+1 r+1 的数量。

如果只对 a a a 进行区间加，那就是一次函数求 min ⁡ min min 。两个序列都要区间加，这怎么做啊……

题解给出一种构造的解法：特殊点构成矩形，当且仅当无穷大平面上 仅有四个 2 × 2 2times 2 2×2 小正方形包含奇数个特殊点。（原话是：有四个小正方形仅包含 1 1 1 个特殊点，下文称为 “角型” ；没有小正方形包含 3 3 3 个特殊点，下文称为 “凹型”。）

为什么呢？用扫描线来说明它吧。从左到右检查每一列。对于有特殊点的第一列，它必须是连续区间，否则将会提供 2 × ( 2times( 2×( 段数 ) ) ) 个角型（第零列和第一列上的小正方形），加上最后一列提供的 2 × ( 2times( 2×( 段数 ) ) ) 个角型（同理），就爆了。

然后第二列呢？设第一列的 y y y 坐标区间是 [ l , r ] [l,r] [l,r]，由于不存在凹型，所以 [ l , r ] [l,r] [l,r] 中只要有一个位置不是特殊点，那么它相邻位置也不是特殊点，一直推广下去就是 [ l , r ] [l,r] [l,r] 均非特殊点。故：要么 [ l , r ] [l,r] [l,r] 全为特殊点，要么全不为特殊点。

而 [ l , r ] [l,r] [l,r] 全不为特殊点时，在 l − 1 l-1 l−1 或 r + 1 r+1 r+1 放置特殊点就会直接提供 1 1 1 个角型（找到 l − 1 l-1 l−1 向下延伸最远的特殊点，它作为小正方形的右上角； r + 1 r+1 r+1 同理），加上最后一列提供 2 2 2 个角型就爆了。所以 l − 1 l-1 l−1 和 r + 1 r+1 r+1 不是特殊点。

这样会导致第一列又提供 2 2 2 个角型（第一列的 l l l 作为小正方形左上角；第一列的 r r r 作为小正方形左下角）。唯一的解决方案就是，第一列就是最后一列，也就是扫描结束！一言以蔽之，上一列不是这一列的子集，只可能是整个图形扫描完毕！

如果 [ l , r ] [l,r] [l,r] 全为特殊点呢？那么 l − 1 , r + 1 l-1,r+1 l−1,r+1 不是特殊点，否则出现凹型。更外面就同样无法出现特殊点了，否则角型数量超标。那么第二列和第一列完全相同。

显然上面的分析不局限于第一列和第二列的讨论。所以这样一定是矩形！

上面的分析同样说明，角型至少有 4 4 4 个，所以可以等价于角型 + + + 凹型只有 4 4 4 个。对于值域右端点 r r r，线段树维护值域左端点 l l l 对应的角型 + + + 凹型的数量，查询最小值的数量与 l l l 的和。

渐进复杂度 O ( N log ⁡ N ) mathcal O(Nlog N) O(NlogN)，但是 2 × 2 2times 2 2×2 小正方形会提供 10 10 10 次操作，且 N = ( n + 1 ) ( m + 1 ) N=(n+1)(m+1) N=(n+1)(m+1)，运行速度与一般意义上的 O ( N log ⁡ 2 N ) mathcal O(Nlog^2N) O(Nlog2N) 差不多……

代码

相当卡常。我甚至不得不将线段树的递归改为循环……

# pragma GCC optimize("Ofast")
#include <cstdio>
#include <iostream>
#include <vector>
#include <cstring>
#include <algorithm>
using namespace std;
# define rep(i,a,b) for(int i=(a); i<=(b); ++i)
# define drep(i,a,b) for(int i=(a); i>=(b); --i)
typedef long long int_;
const int __buffer_length = 1290240;
char in_buf[__buffer_length];
inline char getChar(){static char *S = in_buf, *T = S;if(T == S) S = in_buf, T = S +fread(S,1,__buffer_length,stdin);return *(S ++);
}
inline int readint(){int a = 0; char c = getChar(), f = 1;for(; c<'0'||c>'9'; c=getChar())if(c == '-') f = -f;for(; '0'<=c&&c<='9'; c=getChar())a = (a<<3)+(a<<1)+(c^48);return a*f;
}
inline void writeint(int x){if(x > 9) writeint(x/10);putchar((x-x/10*10)^48);
}
# define swapInt(a,b) (a) ^= (b) ^= (a) ^= (b)
inline void bubbleSort(int *l,int *r){for(; r!=l; --r){bool ok = true;int *i = l, *j = i+1;for(; j!=r; ++i,++j)if((*i) > (*j)){swapInt(*i,*j);ok = false;}if(ok) return ;}
}const int MaxN = 200005;
struct MyList{int nxt, l, r;
};
MyList mem[MaxN*20];
int head[MaxN], cntList;
inline void pushBack(int id,int L,int R){mem[cntList].nxt = head[id];mem[cntList].l = L, mem[cntList].r = R;head[id] = cntList ++;
}const int Mod = 998244353;
inline void add(int &x,const int &y){(x += y) >= Mod ? (x -= Mod) : 0;
}int tot_len;
namespace SgTree{const int MaxM = MaxN<<2;int mn[MaxM], lazy[MaxM];int sum[MaxM], cnt[MaxM];inline void addNode(int o,int x){mn[o] += x, lazy[o] += x;}void pushDown(int o){if(lazy[o] == 0) return ;addNode(o<<1|1,lazy[o]);addNode(o<<1,lazy[o]), lazy[o] = 0;}void pushUp(int o){int d = (mn[o<<1] > mn[o<<1|1]);mn[o] = mn[(o<<1)|d];cnt[o] = cnt[(o<<1)|d];sum[o] = sum[(o<<1)|d];if(mn[o<<1] == mn[o<<1|1]){cnt[o] += cnt[o<<1|1];add(sum[o],sum[o<<1|1]);}}# define LSON o<<1,l,(l+r)>>1# define RSON o<<1|1,((l+r)>>1)+1,rvoid build(int o=1,int l=1,int r=tot_len){while(true){ // recurse -> loopmn[o] = Mod, cnt[o] = r-l+1, lazy[o] = 0;if(l == r){ sum[o] = l; break; }build(RSON); sum[o] = sum[o<<1|1];o <<= 1; r = (l+r)>>1; // goto LSON}for(; !(o&1); o>>=1) add(sum[o>>1],sum[o]);}void modify(int ql,int qr,int qv,int o=1,int l=1,int r=tot_len){while(true){ // recurse -> loopif(qr < l || r < ql) break;if(ql <= l && r <= qr){addNode(o,qv); break;}pushDown(o); modify(ql,qr,qv,RSON);o <<= 1; r = (l+r)>>1; // goto LSON}while(!(o&1)) pushUp(o >>= 1);}inline int queryCnt(){ return cnt[1]; }inline int querySum(){ return sum[1]; }
}int *a[MaxN], b[5];
int main(){int n = readint(), m = readint();rep(i,1,n){a[i] = new int[m+2];*a[i] = a[i][m+1] = -1;}a[0] = new int[m+2];memset(a[0],-1,(m+2)<<2);a[n+1] = new int[m+2];memset(a[n+1],-1,(m+2)<<2);rep(i,1,n) rep(j,1,m)a[i][j] = readint();tot_len = n*m; SgTree::build();memset(head+1,-1,tot_len<<2);rep(i,0,n) rep(j,0,m){b[0] = a[i][j], b[1] = a[i][j+1];b[2] = a[i+1][j], b[3] = a[i+1][j+1];bubbleSort(b,b+4); // [l,r]int lst = 1; // where fromrep(l,0,3) if(~b[l]){rep(r,l,3) // [lst,b_l]if((r^l)&1) pushBack(b[r],lst,-b[l]);else pushBack(b[r],lst,b[l]);lst = b[l]+1; // move on}}int ans = 0;for(int i=1; i<=(tot_len); ++i){for(int j=head[i]; ~j; j=mem[j].nxt)if(mem[j].r < 0) // deleteSgTree::modify(mem[j].l,-mem[j].r,-1);else SgTree::modify(mem[j].l,mem[j].r,1);SgTree::modify(i,i,-Mod); // releaseans = (ans+int_(i+1)*SgTree::queryCnt())%Mod;add(ans,Mod-SgTree::querySum());}printf("%dn",ans);return 0;
}

后记

p r i n c i p a l rm principal principal 出了这道题，感到心满意足。这可是一道难度高达 2 31 − 1 2^{31}-1 231−1 的题目！

p r i n c i p a l rm principal principal 即使想到 O n e I n D a r k sf OneInDark OneInDark 把 O I OI OI 的风气都带坏了，也没有像他一样无耻地笑出声，实在是时代楷模！