题意
给出长度为n的序列a，问有多少种子序列满足首元素< =尾元素
思路：
假设现在已经确定了首元素的下标为x xx，尾元素的下标为y，那么方案数为2y−x−1。中间的每个元素都有选/不选两种可能性。
问题转化成了∑ 1 < = x < = y < = n 2 y − x − 1 [ a x < = a y ]
考虑每个元素的贡献，假设现在枚举到元素y，那么这个元素的贡献就是2 y − 1 ∗ ∑ ( 1 2 ) x计算完总贡献后计算该元素对后面元素的贡献，加上( 1 /2 ) y将1/2
转化为逆元，用树状数组维护。
代码：
// Problem: E - LEQ // Contest: AtCoder - AtCoder Beginner Contest 221 // URL: https://atcoder.jp/contests/abc221/tasks/abc221_e // Memory Limit: 1024 MB // Time Limit: 2000 ms // // Powered by CP Editor (https://cpeditor.org) #include<bits/stdc++.h> using namespace std; typedef long long ll;typedef unsigned long long ull; typedef pair<ll,ll>PLL;typedef pair<int,int>PII;typedef pair<double,double>PDD; #define I_int ll inline ll read(){ll 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*10+ch-'0';ch=getchar();}return x*f;} #define read read() #define rep(i, a, b) for(int i=(a);i<=(b);++i) #define dep(i, a, b) for(int i=(a);i>=(b);--i) ll ksm(ll a,ll b,ll p){ll res=1;while(b){if(b&1)res=res*a%p;a=a*a%p;b>>=1;}return res;} const int maxn=4e5+7,maxm=1e6+7,mod=998244353; int a[maxn],tr[maxn],n; vector<int>nums; int lowbit(int x){ return x&-x; } void update(int pos,int val){ while(pos<=n) tr[pos]=(val+tr[pos])%mod,pos+=lowbit(pos); } int query(int pos){ int ans=0; while(pos) ans=(ans+tr[pos])%mod,pos-=lowbit(pos); return ans; } int main(){ n=read; rep(i,1,n) a[i]=read,nums.push_back(a[i]); sort(nums.begin(),nums.end()); nums.erase(unique(nums.begin(),nums.end()),nums.end()); rep(i,1,n){ a[i]=lower_bound(nums.begin(),nums.end(),a[i])-nums.begin()+1; } int ans=0,t=ksm(2,mod-2,mod); rep(i,1,n){ ans=(ans+ksm(2,i-1,mod)*query(a[i])%mod)%mod; update(a[i],ksm(t,i,mod)); } cout<<ans<<endl; return 0; }
