题目背景
夹带力度！
题目描述
给出整数序列 $a_1,\ldots,a_n$，求有多少个 $a$ 的排列 $a'$ 使得 $\sum_{1\le l\le r\le n}\min_{l\le i\le r}a'_i$ 最大。
对于一个序列 $a$，它的排列指将元素按照某种方式重新排列得到的序列。一个权值在原序列的出现次数和排列中出现的次数应该是相同的。例如 1 4 4 1 1 5 就是 1 1 4 5 1 4的一个排列。
两个排列不同当且仅当他们在某一位上的数不同。
……这样会不会太简单了？
那么就加一个区间修改吧！有 $m$ 次操作：
l r k把区间 $[l, r]$ 的数全部变成 $k$。
第一次修改前，以及每次修改后，你都需要输出答案。
……不想写高精度？
那就对 $998244353$ 取模吧。
读入格式
第一行两个数 $n, m$。
接下来 $n$ 个数表示 $a_1, \ldots, a_n$。
接下来 $m$ 行每行三个数 $l_i, r_i, k_i$。
输出格式
$m + 1$ 行每行一个数表示答案。
样例
5 40
2 3 5 4 2
5 5 5
2 3 2
4 5 1
4 4 2
3 3 1
1 4 5
3 5 4
2 5 2
2 5 3
4 4 2
3 3 4
1 1 4
1 4 2
1 5 4
2 4 5
4 4 3
5 5 1
1 2 1
2 5 5
5 5 2
4 4 3
3 4 4
1 5 3
5 5 3
5 5 3
3 5 5
4 4 2
1 2 2
2 5 1
3 4 5
4 5 1
3 3 3
3 3 1
5 5 5
2 4 5
4 5 4
2 2 5
2 5 5
5 5 3
5 5 512
8
8
3
2
3
2
4
5
5
8
12
6
5
1
3
6
8
8
2
4
8
12
1
1
1
3
6
4
5
6
8
8
5
8
2
6
6
2
4
2提示
没有提示。
数据范围
- 对于 20% 的数据 $n\le 100$。
- 对于 40% 的数据 $n\le 1000$。
- 对于 60% 的数据 $n\le 5000$。
- 对于 80% 的数据 $n\le 10^5$。
此外对于所有编号为偶数的测试点，有 $m = 0$。
对于所有数据 $1\le n, m\le 2\times 10^5, 1\le a_i, l, r, k\le n$。
首先考虑不带修。很明显，如果我们每次把最小值放到边缘，才会最优。然后就可以递归下去。而放边缘时，我们可以控制他放左边还是放右边，如果一个数 \(i\) 出现了 \(c_i\) 次，那么他的方案数就是 \(\frac{\prod (c_i+1)}{c_{mx}+1}\)。
上面这个东西很容易可以求出来。那么我们考虑如何带修。修改是区间覆盖，所以我们可以用线段树或者 ODT 。我用了线段树。忽略除以 \(c_{mx}+1\) 每次覆盖时对于整一段一样的，一起修改答案，并进行区间覆盖。最后后答案除以最大值出现次数加一。
#include<bits/stdc++.h>
using namespace std;
const int N=8e5+5,P=998244353;
int n,m,a[N],l,r,k,mx[N],tag[N],ans(1),inv[N],cnt[N],mn[N];
void add(int x,int k)
{
ans=1LL*ans*inv[cnt[x]+1]%P;
cnt[x]+=k;
ans=1LL*ans*(cnt[x]+1)%P;
}
void pushdown(int o,int l,int r)
{
if(mx[o]==mn[o])
mx[o<<1]=mx[o<<1|1]=mn[o<<1]=mn[o<<1|1]=mx[o];
}
void update(int o,int l,int r,int x,int y,int k)
{
if(x<=l&&r<=y&&mx[o]==mn[o])
{
add(mx[o],l-r-1);
mx[o]=mn[o]=k;
return;
}
pushdown(o,l,r);
int md=l+r>>1;
if(md>=x)
update(o<<1,l,md,x,y,k);
if(md<y)
update(o<<1|1,md+1,r,x,y,k);
mx[o]=max(mx[o<<1],mx[o<<1|1]);
mn[o]=min(mn[o<<1],mn[o<<1|1]);
}
int main()
{
scanf("%d%d",&n,&m),inv[1]=1;
cnt[0]=n,ans=n+1;
for(int i=2;i<=n+1;i++)
inv[i]=1LL*(P-P/i)*inv[P%i]%P;
for(int i=1;i<=n;i++)
{
scanf("%d",a+i);
update(1,1,n,i,i,a[i]);
add(a[i],1);
}
printf("%d\n",1LL*ans*inv[cnt[mx[1]]+1]%P);
for(int i=1;i<=m;i++)
{
scanf("%d%d%d",&l,&r,&k);
update(1,1,n,l,r,k);
add(k,r-l+1);
printf("%d\n",1LL*ans*inv[cnt[mx[1]]+1]%P);
}
}