次方计数的拆贡献法（考虑组合意义）+限定类问题善用值域与位置进行ds：1006T3

本文搬运自本人高中时期CSDN博客，若图片加载不出来，可到原文查看：https://blog.csdn.net/zhangtingxiqwq/article/details/133621275

对于多次方的计数问题可以考虑拆贡献。

题目问 $|S|^3$ ， $|S|$ 表示选的点数。相当于在 $|S|$ 中选了3次，也就是选了3个可相同的点。

先考虑3个不相同点的贡献，对应任意3个点，必然会对所有包含其矩形产生贡献。所以只需要统计对应的矩形数目。但是必须乘上全排列6，因为我们钦定选了3次是考虑顺序的。

对于2个同，3个同同理。都会对相应矩形产生贡献。

现在考虑统计3个点的情况，发现本质有两种：

这种很好统计，直接ds维护。

这种我们拿ds维护的时候，很容易出现算错的现象。因为我们计算贡献的顺序可能是这样的：

那就会把这种情况算进去：

而用这种方法计算则不会出现问题，因为我们放在了两边

//5.7k

#include<bits/stdc++.h>
using namespace std;
#define int long long
inline int read(){int x=0,f=1;char ch=getchar(); while(ch<'0'||
ch>'9'){if(ch=='-')f=-1;ch=getchar();}while(ch>='0'&&ch<='9'){
x=(x<<1)+(x<<3)+(ch^48);ch=getchar();}return x*f;}
#define Z(x) (x)*(x)
#define pb push_back
//mt19937 rand(time(0));
//mt19937_64 rand(time(0));
//srand(time(0));
#define N 100010
//#define M
#define mo 998244353
struct Node {
	int x, id; 
}b[N];
int n, m, i, j, k, T;
int ans1, ans2, ans3; 
int mx, p[N], a[N], rt; 

int calc1() {
	int ans=0; 
	for(i=1; i<=n; ++i) {
		ans+=i*(n-i+1)%mo*p[i]%mo*(n-p[i]+1)%mo; 
		ans%=mo; 
	}
	return ans; 
}

void Add(int &a, int b) {
	a+=b; a%=mo; 
}

void Mul(int &a, int b) {
	a*=b; a%=mo; 
}

struct Binary_tree {
	int cnt[N], i; 
	void clear() {
		for(i=0; i<=n; ++i) cnt[i]=0; 
	}
	void add(int x, int y) {
//		printf("> %d\n", x); 
		while(x<=n) Add(cnt[x], y), x+=x&-x; 
	}
	int que(int x) {
//				printf("> %d\n", x); 

		int ans=0; 
		while(x) Add(ans, cnt[x]), x-=x&-x; 
		return ans; 
	}
}Bin, Bin1, Bin2;

int suan() {
	int i, ans=0; 
	Bin.clear(); 
	for(i=1; i<=n; ++i) {
		Add(ans, Bin.que(a[i])*(n-i+1)%mo*(n-a[i]+1)%mo);  
		Bin.add(a[i], a[i]*i%mo); 
	}
	return ans; 
}

int calc2() {
	int ans=0; 
	ans+=suan(); 
	for(i=1; i<=n; ++i) a[i]=n-a[i]+1; 
	ans+=suan(); ans%=mo; 
	return ans; 
}

int suan31() {
	int ans=0, i; 
	Bin1.clear(); Bin2.clear(); 
	for(i=1; i<=n; ++i) Bin2.add(a[i], (n-i+1)*(n-a[i]+1)%mo); 
	for(i=1; i<=n; ++i) {
		Bin2.add(a[i], -(n-i+1)*(n-a[i]+1)%mo); 
		Add(ans, Bin1.que(a[i])*(Bin2.que(n)-Bin2.que(a[i]))); 
//		printf("%lld : %lld\n", i, ans); 
		Bin1.add(a[i], i*a[i]%mo); 
	}
	return ans; 
}

struct Segment_tree {
	int tot, ls[N<<2], rs[N<<2]; 
	int s[N<<2], c[N<<2], tag[N<<2]; 
	void clear(int &k, int l, int r) {
		if(!k) k=++tot, s[k]=c[k]=tag[k]=ls[k]=rs[k]=0; 
		if(l==r) return ; 
		int mid=(l+r)>>1; 
		clear(ls[k], l, mid); clear(rs[k], mid+1, r); 
	}
	void push_down(int k) {
		Add(tag[ls[k]], tag[k]); Add(tag[rs[k]], tag[k]); 
		Add(s[ls[k]], c[ls[k]]*tag[k]%mo); 
		Add(s[rs[k]], c[rs[k]]*tag[k]%mo); 
		tag[k]=0; 
	}
	void push_up(int k) {
		s[k]=(s[ls[k]]+s[rs[k]])%mo; 
		c[k]=(c[ls[k]]+c[rs[k]])%mo; 
	}
	void add(int k, int l, int r, int x, int y) {
//		printf("Add : %lld %lld\n", x, y); 
		if(l==r) {
			Add(c[k], y);
//			printf("Then c[%lld] become %lld\n", k, c[k]); 

			return  void(); 
		}
//		printf("s[%lld]=%lld [%lld %lld]\n", k, s[k], x, y); 

		push_down(k); 
//		printf("s[%lld]=%lld [%lld %lld]\n", k, s[k], x, y); 

		int mid=(l+r)>>1; 
		if(x<=mid) add(ls[k], l, mid, x, y); 
		else add(rs[k], mid+1, r, x, y);
//		printf("s[%lld]=%lld [%lld %lld]\n", k, s[k], x, y); 
 
		push_up(k); 
//		printf("s[%lld]=%lld [%lld %lld]\n", k, s[k], x, y); 
//		printf("Then c[%lld] become %lld\n", k, c[k]); 
	}
	void modify(int k, int l, int r, int x, int y, int z) {
		if(l>=x && r<=y) {
			Add(s[k], c[k]*z%mo), Add(tag[k], z); 
//			printf("==== [%lld] %lld %lld\n", k, s[k], c[k]); 
//			return Add(s[k], c[k]*z%mo), Add(tag[k], z), void();
			return ;  
		}
			
		int mid=(l+r)>>1; push_down(k);  
		if(x<=mid) modify(ls[k], l, mid, x, y, z); 
		if(y>=mid+1) modify(rs[k], mid+1, r, x, y, z); 
		push_up(k); 
//		printf(">>> s[%lld]=%lld [%lld %lld]\n", k, s[k], x, y); 

//		printf("")
	}
	int que(int k, int l, int r, int x, int y) {
		if(l>=x && r<=y) return s[k]; 
		int mid=(l+r)>>1, sum=0; push_down(k); 
		if(x<=mid) sum+=que(ls[k], l, mid, x, y); 
		if(y>=mid+1) sum+=que(rs[k], mid+1, r, x, y); 
		return sum%mo; 
	}
}Seg;

int suan32() {
	int ans=0, i; 
//	for(i=1; i<=n; ++i) printf("%lld ", a[i]); printf(" => "); 
////	Bin1.clear(); Bin2.clear(); 
//	for(i=1; i<=n; ++i) {
//		Add(ans, (n-i+1)*Bin2.que(a[i])%mo); 
//		printf("%lld : %lld %lld\n", (n-i+1)*Bin2.que(a[i]), a[i]*(Bin1.que(n)-Bin1.que(a[i]))); 
//		Bin2.add(a[i], a[i]*(Bin1.que(n)-Bin1.que(a[i]))%mo); 
//		Bin1.add(a[i], i*(n-a[i]+1)%mo); 
//	}
	for(i=1; i<=n; ++i) b[i].x=a[i], b[i].id=i; 
	sort(b+1, b+n+1, [] (Node x, Node y) { return x.x>y.x; }); 
	rt=Seg.tot=0; Seg.clear(rt, 1, n); 
	for(i=1; i<=n; ++i) {
		Add(ans, b[i].x*(n-b[i].id+1)%mo*Seg.que(1, 1, n, 1, b[i].id)%mo); 
//		printf("%lld[%lld %lld] : %lld %lld %lld\n", i, 
//			b[i].id, b[i].x, b[i].x*(n-b[i].id+1), Seg.que(1, 1, n, 1, b[i].id), 
//					b[i].x*(n-b[i].id+1)%mo*Seg.que(1, 1, n, 1, b[i].id)%mo); 
		Seg.modify(1, 1, n, b[i].id, n, b[i].id); 
		Seg.add(1, 1, n, b[i].id, n-b[i].x+1); 
	}
//	printf("%lld\n", ans); 
	return ans; 
}

int calc3() {
	int ans=0, i; 
	memcpy(a, p, sizeof(a)); 
	Add(ans, suan31()); 
	for(i=1; i<=n; ++i) a[i]=n-a[i]+1; 
	Add(ans, suan31()); 
//	printf("%lld (%lld)\n", ans, ans*6); 
	memcpy(a, p, sizeof(a)); 
	Add(ans, suan32()); 
	reverse(a+1, a+n+1); 
	Add(ans, suan32()); 
	for(i=1; i<=n; ++i) a[i]=n-a[i]+1; 
	Add(ans, suan32()); 
	reverse(a+1, a+n+1); 
	Add(ans, suan32()); 
//	printf("%lld (%lld)\n", ans, ans*6); 
	return ans; 
//	return 0; 
}

signed main()
{
//	freopen("in.txt", "r", stdin);
//	freopen("out.txt", "w", stdout);
		freopen("points.in", "r", stdin);
	freopen("points.out", "w", stdout);
//	T=read();
//	while(T--) {
//
//	}	
	n=read(); mx=read(); 
	for(i=1; i<=n; ++i) p[i]=a[i]=read(); 
	ans1=calc1(); ans2=calc2(); ans3=calc3(); 
//	printf("Basic : %lld\n", ans1+ans2*6); 
	if(mx==1) return printf("%lld ", ans1), 0; 
	if(mx==2) return printf("%lld ", (ans1+2*ans2)%mo), 0; 
	if(mx==3) return printf("%lld ", (ans1+6*ans2+6*ans3)%mo), 0; 
	return 0;
}