(來源：XJ高質(zhì)量原創(chuàng)題)

原題地址

弱化版：CF526F Pudding Monsters

弱化版

題意：\(n\times n\) 的棋盤上有 \(n\) 顆棋子，每行每列都有且僅有一顆棋子，求出有多少個(gè) \(k\times k\) 的子棋盤也滿足每行每列只有一顆棋子。

將棋盤的 \(x\) 軸看作上一題中每個(gè)點(diǎn)的下標(biāo)，\(y\) 軸看作這個(gè)點(diǎn)的權(quán)值。

其實(shí)就是樹退化為了鏈，而 \(m=1\) 的情況。

題意

給定一棵樹，每一個(gè)點(diǎn)有一個(gè)權(quán)值 \(a_i\) ，\(\{a\}\) 構(gòu)成一個(gè)排列。

詢問有多少個(gè)點(diǎn)集 \(S={u_1,u_2,\dots,u_k}(1\le j\le n)\) 滿足這些點(diǎn)構(gòu)成聯(lián)通塊不超過 \(m\) 個(gè)，且 \(\max_{1\le i\le k}\{a_{u_{i}}\}-\min_{1\le i\le k}\{a_{u_{i}}\}+1=k\) 。

\(n\le 10^5,m\le 7\)

題解

考慮枚舉值域的右端點(diǎn) \(r\)，考慮加入這個(gè)右端點(diǎn)時(shí)，對(duì)與 \([1,r-1]\) 中的最短點(diǎn)的聯(lián)通塊個(gè)數(shù)的變化。

先假設(shè)假設(shè)這個(gè)點(diǎn)與其他無邊相連，那么聯(lián)通塊數(shù)加 \(1\) 。

對(duì)于每一條與點(diǎn)集中的點(diǎn)相連的邊 \((num(r),ver)\) ，都會(huì)使左端點(diǎn)在 \([1,val(ver)]\) 中的聯(lián)通塊數(shù)量 \(-1\) (\(num(x)\) 表示權(quán)值為 \(x\) 的點(diǎn)的編號(hào))。

之后我們就將題意簡(jiǎn)化為：

• 區(qū)間加上一個(gè)數(shù)

• 求出整個(gè)數(shù)列中 \(\le m\) 的數(shù)有多少個(gè)

• 保證 \(a[1]=1\)

考慮到 \(m\) 比較小，猜測(cè)答案復(fù)雜度為 \(O(nm\log n)\) 。

我們將加減操作同普通的線段樹操作，主要改變 \(\text{pushup}\) 操作。

在線段樹的每一個(gè)節(jié)點(diǎn) \([l,r]\) 上維護(hù)：

• \(minn\) ： 表示在 \([l,r]\) 區(qū)間上數(shù)的最小值。

• \(cnt[7]\) ： 表示這段區(qū)間內(nèi)值域在 \([minn,minn+6]\) 之間的數(shù)分別有多少。

之后根據(jù)兩個(gè)子區(qū)間的最小值就可以愉快地轉(zhuǎn)移啦！！

// Author:A weak man named EricQian // expect : 100 pts #include<bits/stdc++.h> using namespace std; #define infll 0x7f7f7f7f7f7f7f7f #define inf 0x3f3f3f3f #define Maxn 500005 #define Maxm 7 typedef long long ll; inline int rd() {int x=0;char ch,t=0;while(!isdigit(ch = getchar())) t|=ch=='-';while(isdigit(ch)) x=x*10+(ch^48),ch=getchar();return x=t?-x:x; } int n,m,tot; int val[Maxn],num[Maxn]; int hea[Maxn],nex[Maxn<<1],ver[Maxn<<1]; struct TREE { ll minn,laz,cnt[Maxm]; }tree[Maxn<<2]; ll ans; inline void add(int x,int y){ ver[++tot]=y,nex[tot]=hea[x],hea[x]=tot; } inline void pushup(int p) {int x=p<<1,y=p<<1|1,tmp;if(tree[x].minn>tree[y].minn) swap(x,y);tree[p].minn=tree[x].minn;for(int i=0;i<m;i++) tree[p].cnt[i]=tree[x].cnt[i];tmp=tree[y].minn-tree[x].minn;for(int i=tmp;i<m;i++) tree[p].cnt[i]+=tree[y].cnt[i-tmp]; } inline void pushdown(int p) {tree[p<<1].laz+=tree[p].laz,tree[p<<1].minn+=tree[p].laz;tree[p<<1|1].laz+=tree[p].laz,tree[p<<1|1].minn+=tree[p].laz;tree[p].laz=0; } void build(int p,int nl,int nr) {if(nl==nr) { tree[p].minn=tree[p].cnt[0]=1; return; }int mid=(nl+nr)>>1;build(p<<1,nl,mid),build(p<<1|1,mid+1,nr);pushup(p); } void add(int p,int nl,int nr,int l,int r,int k) {if(nl>=l && nr<=r) { tree[p].minn+=k,tree[p].laz+=k; return; }pushdown(p);int mid=(nl+nr)>>1;if(mid>=l) add(p<<1,nl,mid,l,r,k);if(mid<r) add(p<<1|1,mid+1,nr,l,r,k);pushup(p); } int main() {n=rd(),m=rd();for(int i=1;i<=n;i++) val[i]=rd(),num[val[i]]=i;for(int i=1,x,y;i<n;i++) x=rd(),y=rd(),add(x,y),add(y,x);build(1,1,n);for(int r=1;r<=n;r++){if(r!=1) add(1,1,n,1,r-1,1);for(int i=hea[num[r]];i;i=nex[i])if(val[ver[i]]<val[num[r]])add(1,1,n,1,val[ver[i]],-1);for(int i=0;i<m;i++) ans+=tree[1].cnt[i];ans-=(n-r);}printf("%lld\n",ans);return 0; }

總結(jié)

以上是生活随笔為你收集整理的【做题记录】max-min+1=len 区间计数的全部?jī)?nèi)容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網(wǎng)站內(nèi)容還不錯(cuò)，歡迎將生活随笔推薦給好友。