P11390 [COCI 2024/2025 #1] 教師 / U?iteljica 題解

知識點

線段樹，掃描線，容斥，狀壓，線段樹分治。

分析

首先可以很容易的看出這題和掃描線有關，把 \([l,r]\) 轉換成圖形上的點即可。我們直接看到子任務 3，滿足特殊性質 B：\(k = 1\)。

那么這個就是把每個數(shù)字單獨拎出來，然后把合法的矩形并在一起，最后求矩形面積并，掃描線解決很簡單。

法 1：容斥

這個解法的題解是網(wǎng)上最多的，對于擅長組合數(shù)學的同學們很友好。

我們從剛剛的部分分進一步推理：發(fā)現(xiàn) \(k>1\) 時，就是把 \(k\) 不同時的矩形并再取交集，然后再算面積。那么這個“并”“交”讓人想到了容斥，所以容斥把「取交集」變成多次的「求并集」解決即可。

由于其他題解討論的都較為詳細，這里不再贅述。

時間復雜度 \(O(k2^kn\log_2{n})\)，空間復雜度 \(O(nk)\)。

法 2：線段樹分治+狀壓

對于不擅長組合數(shù)學的同學們，這個做法可能會友好一點。

我們考慮不用容斥直接「取交集」。仍然是從部分分衍生出來，發(fā)現(xiàn)標記下傳的線段樹在矩形減操作時不太方便，于是可以想到線段樹分治，避免矩形減操作。

再考慮狀壓來存儲線段樹上每個節(jié)點和其子節(jié)點已經(jīng)滿足的 \(k\)，那么很容易就可以解出來：線段樹上每個節(jié)點存覆蓋到自己的區(qū)間矩形加的狀態(tài)，開 \(2^k\) 大小的數(shù)組來存子樹代表的區(qū)間中每種狀態(tài)的數(shù)量。

時間復雜度 \(O(k2^kn\log^2_2{n})\)，空間復雜度 \(O(n2^k)\)。可能需要卡常。

法 3：永久化標記+狀壓

起始思路與法 2 類似。考慮部分分的線段樹實現(xiàn)方法，我們可以標記下傳，也可以標記永久化，而標記永久化明顯十分簡潔，所以我們考慮在正解也用標記永久化。那么就直接正常的掃描線掃過去即可。

時間復雜度 \(O(k2^kn\log_2{n})\)，空間復雜度 \(O(n2^k)\)。

大概是因為矩形只用加一次，導致這個做法是常數(shù)最小的，翻 Luogu 的提交記錄，排名在前面的我有看到的都是這么寫的。

代碼

這里實現(xiàn)了永久化標記線段樹配狀壓的做法。

#include<bits/stdc++.h>
#define INF 0x3f3f3f3f
#define ll long long
#define RCL(a,b,c,d) memset(a,b,sizeof(c)*(d))
#define FOR(i,a,b) for(int i(a);i<=(int)(b);++i)
#define DOR(i,a,b) for(int i(a);i>=(int)(b);--i)
#define tomax(a,...) ((a)=max({(a),__VA_ARGS__}))
#define tomin(a,...) ((a)=min({(a),__VA_ARGS__}))
#define EDGE(g,i,x,y) for(int i=(g).h[(x)],y=(g)[(i)].v;~i;y=(g)[(i=(g)[i].nxt)>0?i:0].v)
#define main Main();signed main(){ios::sync_with_stdio(0);cin.tie(0),cout.tie(0);return Main();}signed Main
using namespace std;
constexpr int N(1e5+10),K(4),St(1<<4);

int n,m,U,tot;
int a[N];
ll ans;
vector<int> vec[N];
struct Line {
	int x,l,r,v,k;

	friend bool operator <(Line a,Line b) { return a.x<b.x; }
} lin[N<<3];
struct SEG {
	struct node {
		int sta;
		int cnt[K],sum[St];
		node(int sta=0):sta(sta) { RCL(cnt,0,int,m),RCL(sum,0,int,U+1); }

		void down(int k,int d) {
			if(cnt[k])sta^=1<<k;
			cnt[k]+=d;
			if(cnt[k])sta^=1<<k;
		}
	} tr[N<<2];
#define ls (p<<1)
#define rs (p<<1|1)
#define mid ((l+r)>>1)
	void Up(int p) {
		RCL(tr[p].sum,0,int,U+1);
		FOR(S,0,U)tr[p].sum[tr[p].sta|S]+=tr[ls].sum[S]+tr[rs].sum[S];
	}

	void Build(int p=1,int l=1,int r=n) {
		tr[p]=node(0);
		if(l==r)return tr[p].sum[0]=1,void();
		Build(ls,l,mid),Build(rs,mid+1,r),Up(p);
	}

	void Plus(int L,int R,int k,int d,int p=1,int l=1,int r=n) {
		if(L<=l&&r<=R) {
			if(l==r)tr[p].sum[tr[p].sta]=0;
			tr[p].down(k,d),(l<r?Up(p),0:tr[p].sum[tr[p].sta]=1);
			return;
		}
		if(L<=mid)Plus(L,R,k,d,ls,l,mid);
		if(mid<R)Plus(L,R,k,d,rs,mid+1,r);
		Up(p);
	}
#undef ls
#undef rs
#undef mid
} seg;

void Plus(const int k,int xa,int xb,int ya,int yb) {
	lin[++tot]= {xa,ya,yb,1,k},lin[++tot]= {xb+1,ya,yb,-1,k};
}

void Solve(vector<int> &vec,const int k) {
	FOR(i,0,(int)vec.size()-k)
		Plus(k-1,!i?1:vec[i-1]+1,vec[i],vec[i+k-1],i+k>=(int)vec.size()?n:vec[i+k]-1);
}

signed main() {
#ifdef Plus_Cat
	freopen(Plus_Cat ".in","r",stdin),freopen(Plus_Cat ".out","w",stdout);
#endif
	cin>>n>>m;
	FOR(i,1,n)cin>>a[i],vec[a[i]].push_back(i);
	U=(1<<m)-1;
	FOR(i,1,n)if(!vec[i].empty())FOR(k,1,m)Solve(vec[i],k);
	sort(lin+1,lin+tot+1),seg.Build();
	int it(1);
	FOR(i,1,n) {
		while(it<=tot&&lin[it].x<=i)seg.Plus(lin[it].l,lin[it].r,lin[it].k,lin[it].v),++it;
		ans+=seg.tr[1].sum[U];
	}
	cout<<ans<<endl;
	return 0;
}