#include <bits/stdc++.h>//一道线段树题目,还用到了离散化
#define int long long
using namespace std;
const int M = 998244353, N = 2e5 + 10;
struct segmenttree
{
int l, r, x, lazy_jia, lazy_cheng, sum;
} a[N * 4];
struct node
{
int l, r, size;
} ss[N];
int m, n, b[N], ls[N];
map<int, int> p;
void write(int x)
{
if (x < 0)
{
putchar('-');
x = -x;
}
if (x >= 10)
{
write(x / 10);
}
putchar(x % 10 + '0');
}
inline int read()
{
char ch = getchar();
int ret = 0, f = 1;
while (ch < '0' || ch > '9')
{
if (ch == '-')
{
f = -1;
}
ch = getchar();
}
while (ch >= '0' && ch <= '9')
{
ret = (ret << 1) + (ret << 3) + ch - '0';
ch = getchar();
}
return ret * f;
}
void js(int l, int r, int x)
{
a[x].l = l, a[x].r = r, a[x].lazy_cheng = 1;
if (l == r)
{
return;
}
int mid = (l + r) / 2;
js(l, mid, x * 2);
js(mid + 1, r, x * 2 + 1);
a[x].sum = (a[x * 2].sum + a[x * 2 + 1].sum) % M;
}
inline void downop(int x)
{
a[x * 2].sum *= a[x].lazy_cheng;
a[x * 2].sum %= M;
a[x * 2 + 1].sum *= a[x].lazy_cheng;
a[x * 2 + 1].sum %= M;
a[x * 2].sum += a[x].lazy_jia % M * (ss[a[x * 2].r].r - ss[a[x * 2].l].l + 1) % M;
a[x * 2].sum %= M;
a[x * 2 + 1].sum += a[x].lazy_jia % M * (ss[a[x * 2 + 1].r].r - ss[a[x * 2 + 1].l].l + 1) % M;
a[x * 2 + 1].sum %= M;
a[x * 2].lazy_cheng *= a[x].lazy_cheng;
a[x * 2].lazy_cheng %= M;
a[x * 2 + 1].lazy_cheng *= a[x].lazy_cheng;
a[x * 2 + 1].lazy_cheng %= M;
a[x * 2].lazy_jia *= a[x].lazy_cheng;
a[x * 2].lazy_jia %= M;
a[x * 2 + 1].lazy_jia *= a[x].lazy_cheng;
a[x * 2 + 1].lazy_jia %= M;
a[x * 2].lazy_jia += a[x].lazy_jia;
a[x * 2].lazy_jia %= M;
a[x * 2 + 1].lazy_jia += a[x].lazy_jia;
a[x * 2 + 1].lazy_jia %= M;
a[x].lazy_cheng = 1;
a[x].lazy_jia = 0;
}
void jia(int l, int r, int x, int s)
{
if (l > r)
return;
if (a[x].l >= l && a[x].r <= r)
{
a[x].lazy_jia += s;
a[x].lazy_jia %= M;
a[x].sum += s % M * (ss[a[x].r].r - ss[a[x].l].l + 1) % M;
a[x].sum %= M;
return;
}
downop(x);
int mid = (a[x].l + a[x].r) / 2;
if (mid >= l)
{
jia(l, r, x * 2, s);
}
if (mid < r)
{
jia(l, r, x * 2 + 1, s);
}
a[x].sum = (a[x * 2].sum + a[x * 2 + 1].sum) % M;
}
int he(int l, int r, int x)
{
if (l > r)
return 0;
if (a[x].l >= l && a[x].r <= r)
{
return a[x].sum %= M;
}
downop(x);
int mid = (a[x].l + a[x].r) / 2, ret = 0;
if (mid >= l)
{
ret += he(l, r, x * 2) % M;
}
if (mid < r)
{
ret += he(l, r, x * 2 + 1) % M;
ret %= M;
}
return ret % M;
}
void cheng(int l, int r, int x, int s)
{
if (l > r)
return;
if (a[x].l >= l && a[x].r <= r)
{
a[x].sum *= s;
a[x].sum %= M;
a[x].lazy_cheng *= s;
a[x].lazy_cheng %= M;
a[x].lazy_jia *= s;
a[x].lazy_jia %= M;
return;
}
downop(x);
int mid = (a[x].l + a[x].r) / 2;
if (mid >= l)
cheng(l, r, x * 2, s);
if (mid < r)
cheng(l, r, x * 2 + 1, s);
a[x].sum = (a[x * 2].sum + a[x * 2 + 1].sum) % M;
}
signed main()
{
ios::sync_with_stdio(0);
n = read();
for (int i = 1; i <= n; i++)
{
b[i] = read();
ls[i] = b[i];
}
stable_sort(ls + 1, ls + n + 1);
m = unique(ls + 1, ls + n + 1) - ls - 1;
ss[1].l = 1, ss[1].r = ls[1], ss[1].size = ls[1];
for (int i = 2; i <= m; i++)
{
ss[i].l = ls[i - 1] + 1;
ss[i].r = ls[i];
ss[i].size = ls[i] - ls[i - 1];
}
for (int i = 1; i <= m; i++)
{
p[ls[i]] = i;
}
js(1, m, 1);
jia(1, p[b[1]], 1, 1);
for (int i = 2; i <= n; i++)
{
int s = he(1, m, 1);
cheng(p[b[i]] + 1, m, 1, 0);
cheng(1, p[b[i]], 1, -1);
jia(1, p[b[i]], 1, s);
}
write((he(1, m, 1) + M) % M);
return 0;
}
标签:竞赛,return,int,代码,ret,程序员,ch,cheng,sum
From: https://www.cnblogs.com/nyyjshcz/p/17548593.html