首页 > 分享 > [爱拼才会赢]小香猪

[爱拼才会赢]小香猪

萌宠菠菠乐园
2024-12-03 06:09

壹、关于题目 ¶

题目背景

有一只小香猪，它有一种奇怪的癖好 —— 它喜欢被尽可能多的人摸，当然，这个癖好其实也能够满足许多人的欲望。

现在，有一群共 Area=n×m" role="presentation">Area=n×m 个人站成一个矩阵，这个矩阵上坐标为 (i,j)" role="presentation">(i,j) 的人有一个权值 ai,j" role="presentation">ai,j，如果小香猪想要走过一个大小为 r×c" role="presentation">r×c 的矩阵，那么该矩阵需要满足极差恰好为 r×c−1" role="presentation">r×c−1. 当小香猪走过这个 r×c" role="presentation">r×c 的子矩阵，显然地，它会被 r×c" role="presentation">r×c 个人摸。由于小香猪被太多的人摸，它已经爽得神志不清，为了救助它，套套狗需要求出它一共被摸过多少次（同一个人可以反复计算），但是该数很大，它只需要知道该数对 998244353" role="presentation">998244353 取模的结果。不过，即使是这样，套套狗也会知道有多少人摸过小香猪，因为它可以去询问校长。

数据范围

对于 100%" role="presentation">100% 的数据，保证 Area≤2×105" role="presentation">Area≤2×105，且 ai,j" role="presentation">ai,j 互不相同。

贰、关于题解 ¶

据说是 IOI2018−D1T2" role="presentation">IOI2018−D1T2 的改编题？不过做法好像不大一样。

关键转化：一个矩阵满足条件，一定是这个区间内数字都是连续的，因为保证 ai,j" role="presentation">ai,j 互不相同。

考虑判定权值在区间 [l,r]" role="presentation">[l,r] 内的所有数所在的格子是否形成了一个矩形，记这些格子的颜色为黑色，其它的格子颜色为白色。考虑所有的 (n+1)×(m+1)" role="presentation">(n+1)×(m+1) 个 2×2" role="presentation">2×2 的小正方形 (部分超出边界也算)，则所有黑色格子形成一个矩形，当且仅当恰好有 4" role="presentation">4 个小正方形内部有 1" role="presentation">1 个黑色格子，并且没有任何一个小正方形内部有 3" role="presentation">3 个黑色格子。从小到大枚举 r" role="presentation">r，对每个 l≤r" role="presentation">l≤r，记 f(l)" role="presentation">f(l) 表示染黑权值在 [l,r]" role="presentation">[l,r] 内的格子后，有多少小正方形内部有 1" role="presentation">1 个或 3" role="presentation">3 个黑色格子。可以发现有 f(l)≥4,f(r)=4" role="presentation">f(l)≥4,f(r)=4 ，于是只需要对每个 l" role="presentation">l 维护 f(l)" role="presentation">f(l) 最小值，最小值的数目和取得最小值的所有 l" role="presentation">l 之和。每次 r" role="presentation">r 增加 1" role="presentation">1 时，会影响到周边的 4" role="presentation">4 个 2×2" role="presentation">2×2 的小正方形，在线段树上修改即可。时间复杂度 O(Arealog⁡Area)" role="presentation">O(Arealog⁡Area).

不过，如果算上代码实现，可能复杂度大概是 O(Arealog2⁡Area)" role="presentation">O(Arealog2⁡Area) 级别，稍微有点卡常。

叁、关于代码 ¶

# pragma GCC optimize("Ofast") # include <bits/stdc++.h> using namespace std; // # define USING_CSTDIO # define NDEBUG # include <cassert> namespace Elaina { # define rep(i, l, r) for(int i=(l), i##_end_=(r); i<=i##_end_; ++i) # define drep(i, l, r) for(int i=(l), i##_end_=(r); i>=i##_end_; --i) # define fi first # define se second # define mp(a, b) make_pair(a, b) # define Endl putchar('n') typedef unsigned int uint; typedef long long ll; typedef unsigned long long ull; typedef pair <int, int> pii; typedef pair <ll, ll> pll; template <class T> inline T fab(T x) { return x < 0? -x: x; } template <class T> inline void getmin(T& x, const T rhs) { x=min(x, rhs); } template <class T> inline void getmax(T& x, const T rhs) { x=max(x, rhs); } # ifndef USING_CSTDIO inline char freaGET() { # define BUFFERSIZE 5000 static char BUF[BUFFERSIZE], *p1=BUF, *p2=BUF; return p1==p2 && (p2=(p1=BUF)+fread(BUF, 1, BUFFERSIZE, stdin), p1==p2)? EOF: *p1++; # undef BUFFERSIZE } # define CHARGET freaGET() # else # define CHARGET getchar() # endif template <class T> inline T readin(T x) { x=0; int f=0; char c; while((c=CHARGET)<'0' || '9'<c) if(c=='-') f=1; for(x=(c^48); '0'<=(c=CHARGET) && c<='9'; x=(x<<1)+(x<<3)+(c^48)); return f? -x: x; } template <class T> inline void writc(T x, char s='n') { static int fwri_sta[55], fwri_ed=0; if(x<0) putchar('-'), x=-x; do fwri_sta[++fwri_ed]=x%10, x/=10; while(x); while(putchar(fwri_sta[fwri_ed--]^48), fwri_ed); putchar(s); } } using namespace Elaina; const int maxn=2e5; const int inf=0x3f3f3f3f; const int mod=998244353; namespace saya { int mn[maxn<<2|2], cnt[maxn<<2|2], tag[maxn<<2|2]; ll sum[maxn<<2|2]; # define ls (i<<1) # define rs (i<<1|1) # define mid ((l+r)>>1) # define _lhs ls, l, mid # define _rhs rs, mid+1, r inline void pushup(int i) { mn[i]=min(mn[ls], mn[rs]), cnt[i]=0, sum[i]=0; if(mn[i]==mn[ls]) cnt[i]=cnt[ls], sum[i]=sum[ls]; if(mn[i]==mn[rs]) cnt[i]+=cnt[rs], sum[i]+=sum[rs]; } inline void add(int i, int v) { mn[i]+=v, tag[i]+=v; } inline void pushdown(int i) { if(!tag[i]) return; add(ls, tag[i]), add(rs, tag[i]), tag[i]=0; } void build(int i, int l, int r) { tag[i]=0; if(l==r) return mn[i]=inf, cnt[i]=1, sum[i]=l, void(); build(_lhs), build(_rhs), pushup(i); } void modify(int L, int R, int v, int i, int l, int r) { if(L>R) return; if(L<=l && r<=R) return add(i, v); pushdown(i); if(L<=mid) modify(L, R, v, _lhs); if(mid<R) modify(L, R, v, _rhs); pushup(i); } inline void clear(int p, int i, int l, int r) { if(l==r) return mn[i]=0, void(); pushdown(i); if(p<=mid) clear(p, _lhs); else clear(p, _rhs); pushup(i); } # undef ls # undef rs # undef mid # undef _lhs # undef _rhs } // using namespace saya; int n, m, Area; int posi[maxn+5]; // vector< vector<int> >a; int **a; inline void input() { n=readin(1), m=readin(1), Area=n*m; // a=vector< vector<int> >(n+5, vector<int>(m+5, 0)); a=new int*[n+5]; rep(i, 0, n+1) a[i]=new int[m+5]; rep(i, 0, n+1) rep(j, 0, m+1) a[i][j]=0; rep(i, 1, n) rep(j, 1, m) { a[i][j]=readin(1); posi[a[i][j]]=(i-1)*m+j; } } # define sign(i) ((i)&1? (-1): (1)) inline void change(int x, int y, int s) { static int buc[5]={0}; buc[1]=a[x][y], buc[2]=a[x][y+1], buc[3]=a[x+1][y], buc[4]=a[x+1][y+1]; rep(i, 1, 4) rep(j, 1, 3) if(buc[j]>buc[j+1]) swap(buc[j], buc[j+1]); int p=1; for(; buc[p]^s; ++p); rep(i, 1, p) saya::modify(buc[i-1]+1, buc[i], sign(p-i), 1, 1, Area); } signed main() { freopen("data.in", "r", stdin); freopen("user.out", "w", stdout); input(); saya::build(1, 1, Area); ll ans=0; rep(i, 1, Area) { register int r=(posi[i]-1)/m+1, c=(posi[i]-1)%m+1; saya::clear(i, 1, 1, Area); rep(x, -1, 0) rep(y, -1, 0) change(r+x, c+y, i); if(saya::mn[1]==4) ans+=1ll*saya::cnt[1]*(i+1)-1ll*saya::sum[1]; } writc(ans%mod); return 0; }