CF526F Pudding Monsters
题意
给定一个 \(n \times n\) 的棋盘，其中有 \(n\) 个棋子，每行每列恰好有一个棋子。
求有多少个 \(k \times k\) 的子棋盘中恰好有 \(k\) 个棋子。
\(n \le 3 \times 10^5\)。
题解
首先注意到每行每列只有一个数这个性质。
这意味着我们可以将这个二维数组转化为一个一维数组 \(a\)，\(a_i\) 表示第 \(i\) 行的数字在 \(a_i\) 这个位置。
这样就是一个区间统计问题了，容易发现一个区间 \([l,r]\) 符合条件必须满足 \(\max_{l,r}-\min_{l,r}=r-l\) 。
这样的东西思路的切入点其实非常多，这里选择使用扫描线。
对于每一个右端点 \(r\) 来计算合法左端点个数。
乍一看好像不是很好维护，但是仔细想一想之后好像又很平凡。
转化条件变为 \(\max_{l,r}-\min_{l,r}+l-r=0\) 。
对于每一个左端点维护 \(\max_{l,r}-\min_{l,r}+l-r\) 的值，然后统计 \(0\) 的个数。
\(l\) 的值可以在线段树建树的时候就解决。
考虑一个端点向右移动之后的影响，\(r\) 就是区间 \(-1\)。
考虑 \(a_r\) 作为 \(min\) 和 \(max\) 的时候，这显然可以用单调栈解决。
最后就是统计 \(0\) 的问题了，嗯统计肯定不太能用线段树，要用分块之类的东西。
考虑这题的特殊性质 \(\max_{l,r}-\min_{l,r}+l-r \geq 0\)
所以我们将统计区间最小值和最小值的个数，然后统计最小值为 \(0\) 的区间。
为什么这样可以统计？因为减到 \(0\) 的数肯定是最小值，并且到 \(0\) 之后不会更小，所以可以维护。
时间复杂度 \(O(nlogn)\)。
点击查看代码
#include <bits/stdc++.h>
#define int long long
#define rg register
#define pc putchar
#define gc getchar
#define pf printf
#define space pc(' ')
#define enter pc( '\n' )
#define me(x,y) memset(x,y,sizeof(x))
#define pb push_back
#define FOR(i,k,t,p) for(rg int i(k) ; i <= t ; i += p)
#define ROF(i,k,t,p) for(rg int i(k) ; i >= t ; i -= p)
using namespace std ;
inline void read(){}
template<typename T,typename ...T_>
inline void read(T &x,T_&...p)
{
x = 0 ;rg int fk(0) ; rg char c(gc()) ;
while(!isdigit(c)) fk |= (c=='-'),c = gc() ;
while(isdigit(c)) x = (x<<1)+(x<<3)+(c^48),c = gc() ;
x = (fk?-x:x) ;
read(p...);
}
int stk[30],tp ;
inline void print(){}
template<typename T,typename ...T_>
inline void print(T x,T_...p)
{
if(x < 0) pc('-'),x = -x ;
do stk[++tp] = x%10,x /= 10 ; while(x) ;
while(tp) pc(stk[tp--]^48) ; space ;
print(p...) ;
}
const int N = 5e5+5 ;
int n,ans,top1,top2 ;
int a[N],st1[N],st2[N] ;
struct Node{int l,r,mi,w,tag ;}tr[N<<2] ;
#define ls(x) (x<<1)
#define w(x) tr[x].w
#define rs(x) (x<<1|1)
#define mi(x) tr[x].mi
#define tag(x) tr[x].tag
#define mid (tr[x].l+tr[x].r>>1)
inline void f(int x,int k){mi(x) += k,tag(x) += k ;}
inline void update(int x)
{
mi(x) = min(mi(ls(x)),mi(rs(x))),w(x) = 0 ;
w(x) += (mi(x)==mi(ls(x)))?w(ls(x)):0 ;
w(x) += (mi(x)==mi(rs(x)))?w(rs(x)):0 ;
}
inline void pushdown(int x){if(tag(x)) f(ls(x),tag(x)),f(rs(x),tag(x)),tag(x) = 0 ;}
void Build(int x,int le = 1,int ri = n)
{
tr[x] = {le,ri} ; if(le == ri){mi(x) = le,w(x) = 1 ; return ;}
Build(ls(x),le,mid),Build(rs(x),mid+1,ri),update(x) ;
}
void Modify(int x,int le,int ri,int k)
{
if(tr[x].l >= le && tr[x].r <= ri){f(x,k) ; return ;} pushdown(x) ;
if(le <= mid) Modify(ls(x),le,ri,k) ; if(mid < ri) Modify(rs(x),le,ri,k) ; update(x) ;
}
int Query(int x,int le,int ri)
{
if(tr[x].l >= le && tr[x].r <= ri) return (!mi(x))?w(x):0 ; pushdown(x) ; int res = 0 ;
if(le <= mid) res = Query(ls(x),le,ri) ; if(mid < ri) res += Query(rs(x),le,ri) ; update(x) ; return res ;
}
signed main()
{
read(n) ;
FOR(i,1,n,1)
{
int x,w ;
read(x,w),a[x] = w ;
}
Build(1) ;
FOR(i,1,n,1)
{
while(top1 && a[st1[top1]] < a[i]) Modify(1,st1[top1-1]+1,st1[top1],a[i]-a[st1[top1]]),--top1 ;
while(top2 && a[st2[top2]] > a[i]) Modify(1,st2[top2-1]+1,st2[top2],a[st2[top2]]-a[i]),--top2 ;
Modify(1,1,n,-1) ;
st1[++top1] = i,st2[++top2] = i,ans += Query(1,1,i) ;
}
print(ans) ;
return 0 ;
}
ohers
CF997E 是这道题的加强版，还是有点意思。
同样的条件，但是多了个区间询问。
考虑询问区间 \([l,r]\) 在上题的扫描线中是如何得到答案的。
显然是线段树上 \([l,r]\) 在从 \(l\) 扫到 \(r\) 的询问中提供的答案总和。
这是一个区间历史版本和状物的东西。
考虑再次对询问进行扫描线，对每一个 \([l,r]\) 维护在扫描到 \(k\) 的时候的历史版本和。
这题有一个比较特殊的地方，在扫描 \(k\) 的时候，\([k,n]\) 都是不作贡献的，所以这时区间 \([l,r]\) 维护的贡献的其实是 \(l\) 到 \(k\) 的时候。
所以扫描到 \(r\) 的时候线段树上的 \([l,r]\) 就正好是我们需要的。
在线段树上多添加一个系数 \(tag\)，同时再维护历史版本和，每移动一个位置全局加系数即可，时间复杂度仍是 \(O(nlogn)\)。
说实话，这东西有些抽象，还是看代码比较好理解。
点击查看代码
#include <bits/stdc++.h>
#define int long long
#define rg register
#define pc putchar
#define gc getchar
#define pf printf
#define space pc(' ')
#define enter pc( '\n' )
#define me(x,y) memset(x,y,sizeof(x))
#define pb push_back
#define FOR(i,k,t,p) for(rg int i(k) ; i <= t ; i += p)
#define ROF(i,k,t,p) for(rg int i(k) ; i >= t ; i -= p)
using namespace std ;
inline void read(){}
template<typename T,typename ...T_>
inline void read(T &x,T_&...p)
{
x = 0 ;rg int fk(0) ; rg char c(gc()) ;
while(!isdigit(c)) fk |= (c=='-'),c = gc() ;
while(isdigit(c)) x = (x<<1)+(x<<3)+(c^48),c = gc() ;
x = (fk?-x:x) ;
read(p...);
}
int stk[30],tp ;
inline void print(){}
template<typename T,typename ...T_>
inline void print(T x,T_...p)
{
if(x < 0) pc('-'),x = -x ;
do stk[++tp] = x%10,x /= 10 ; while(x) ;
while(tp) pc(stk[tp--]^48) ; space ;
print(p...) ;
}
const int N = 5e5+5 ;
int n,top1,top2,q ;
int a[N],ans[N],L[N],R[N],st1[N],st2[N] ;
struct Node{int l,r,mi,w,tag,sum,ttg ;}tr[N<<2] ;
#define ls(x) (x<<1)
#define w(x) tr[x].w
#define rs(x) (x<<1|1)
#define mi(x) tr[x].mi
#define tag(x) tr[x].tag
#define sum(x) tr[x].sum
#define ttg(x) tr[x].ttg
#define mid (tr[x].l+tr[x].r>>1)
inline void f(int x,int k){mi(x) += k,tag(x) += k ;}
inline void f1(int x,int k){ttg(x) += k,sum(x) += k*w(x) ;}
inline void update(int x)
{
sum(x) = sum(ls(x))+sum(rs(x)) ;
mi(x) = min(mi(ls(x)),mi(rs(x))),w(x) = 0 ;
w(x) += (mi(x)==mi(ls(x)))?w(ls(x)):0 ;
w(x) += (mi(x)==mi(rs(x)))?w(rs(x)):0 ;
}
inline void pushdown(int x)
{
if(tag(x)) f(ls(x),tag(x)),f(rs(x),tag(x));
if(mi(x) == mi(ls(x))) f1(ls(x),ttg(x)) ;
if(mi(x) == mi(rs(x))) f1(rs(x),ttg(x)) ;
ttg(x) = tag(x) = 0 ;
}
void Build(int x,int le = 1,int ri = n)
{
tr[x] = {le,ri} ; if(le == ri){mi(x) = le,w(x) = 1 ; return ;}
Build(ls(x),le,mid),Build(rs(x),mid+1,ri),update(x) ;
}
void Modify(int x,int le,int ri,int k)
{
if(tr[x].l >= le && tr[x].r <= ri){f(x,k) ; return ;} pushdown(x) ;
if(le <= mid) Modify(ls(x),le,ri,k) ; if(mid < ri) Modify(rs(x),le,ri,k) ; update(x) ;
}
int Query(int x,int le,int ri)
{
if(tr[x].l >= le && tr[x].r <= ri) return sum(x) ; pushdown(x) ; int res = 0 ;
if(le <= mid) res = Query(ls(x),le,ri) ; if(mid < ri) res += Query(rs(x),le,ri) ; update(x) ; return res ;
}
vector<int>id[N] ;
signed main()
{
read(n) ;
FOR(i,1,n,1) read(a[i]) ;
read(q) ;
FOR(i,1,q,1) read(L[i],R[i]),id[R[i]].pb(i) ;
Build(1) ;
FOR(i,1,n,1)
{
while(top1 && a[st1[top1]] < a[i]) Modify(1,st1[top1-1]+1,st1[top1],a[i]-a[st1[top1]]),--top1 ;
while(top2 && a[st2[top2]] > a[i]) Modify(1,st2[top2-1]+1,st2[top2],a[st2[top2]]-a[i]),--top2 ;
Modify(1,1,n,-1),f1(1,1),st1[++top1] = i,st2[++top2] = i ;
for(auto pos:id[i]) ans[pos] = Query(1,L[pos],i) ;
}
FOR(i,1,q,1) print(ans[i]),enter ;
return 0 ;
}