Submission #41038273

---

Source Code Expand

#include<bits/stdc++.h>
#define rep(i,a,b) for(int i=(a);i<=(b);i++)
#define per(i,a,b) for(int i=(a);i>=(b);i--)
#define op(x) ((x&1)?x+1:x-1)
#define odd(x) (x&1)
#define even(x) (!odd(x))
#define lc(x) (x<<1)
#define rc(x) (lc(x)|1)
#define lowbit(x) (x&-x)
#define mp(x,y) make_pair(x,y)
typedef long long ll;
typedef unsigned long long ull;
typedef double db;
using namespace std;
const int MAXN=2e5+10;
int n,m,a[MAXN],b[MAXN],arr[MAXN];
ll ans,L[MAXN],R[MAXN];

deque<int>dq;

vector<int>v[MAXN];

struct BIT{
	int t[MAXN];
	void mdf(int x,int v){for(;x<=n;x+=lowbit(x))t[x]+=v;}
	int qry(int x){int S=0;for(;x;x-=lowbit(x))S+=t[x];return S;}
	int qry(int L,int R){return (L>R)?(0):(qry(R)-qry(L-1));}
}bit;

int chk(int L,int R){
	return bit.qry(L+1,R-1)==0;
}

int p[MAXN],q[MAXN],s[2][MAXN],tot;

int qry(int x,int L,int R){
	return (L>R)?(0):(s[x][R]-s[x][L-1]);
}

void calc(int* p,int tot,int v){
	rep(i,1,tot){
		s[0][i] = s[0][i-1]+L[p[i]];
		s[1][i] = s[1][i-1]+R[p[i]];
	}	
	rep(i,m,tot){
		ans += (R[p[i]] * s[0][i-m+1])*v;
	}
}

void calc(){ 
	int x=a[dq.front()]; //值为x
	vector<int>v(0);
	while(dq.size() && a[dq.front()]==x){
		v.push_back(dq.front());
		dq.pop_front();
	}
	sort(v.begin(),v.end());
	
	int sz=v.size();

	if(!sz)return;

	rep(i,0,sz-1)bit.mdf(v[i],-1);

	for(int l=0,r;l<sz;l=r+1){
		r=l;while(r+1<sz && chk(v[l],v[r+1]))r++;
		//合并[l,r]段

		tot=0;rep(i,l,r)p[++tot]=v[i];
		if(tot<m){
			rep(i,1,tot)bit.mdf(p[i],1);
			continue;
		}
		
		for(int i=1;i<=tot;){
			if(b[p[i]]){i++;continue;}
			int cur=0,j=i;
			while(j<tot && !b[p[j+1]])j++;
			rep(k,i,j)q[++cur]=p[k];
			calc(q,cur,-1);
			i=j+1;
		}
		calc(p,tot,1);
		int cnt=tot/m;

		rep(i,1,cnt){
			bit.mdf(p[i],1);

			dq.push_front(p[i]);
			a[p[i]]=x+1;
			b[p[i]]=0;

			L[p[cnt-i+1]]=qry(0,tot-min(tot,m*(i+1)-1)+1,tot-m*i+1);
			R[p[i]]=qry(1,m*i,min(tot,m*(i+1)-1));
		}
	}
}

int main(){
	ios::sync_with_stdio(false);

	cin>>n>>m;
	rep(i,1,n)cin>>a[i];
	iota(arr+1,arr+1+n,1);
	sort(arr+1,arr+1+n,[&](int x,int y){return a[x] < a[y];});
	rep(i,1,n)dq.push_back(arr[i]);

	ans=n;
	rep(i,1,n)bit.mdf(i,1),b[i]=1;

	rep(i,1,n)L[i]=R[i]=1;
	
	while(dq.size())calc();

	cout<<ans<<endl;

    return 0;
}

Submission Info

Judge Result