生活随笔
收集整理的這篇文章主要介紹了
E - LEQ(树状数组)
小編覺得挺不錯的,現在分享給大家,幫大家做個參考.
E - LEQ
題意：給一個數組，找出有多少子序列 滿足a1<ak
思路：易知，對于一對數 ai<aj 子序列的數量為2(j-i-1) 即 2j-1/2i 若ai<aj<ak, ak的貢獻為 2k-1(1/2i+1/2j)
則可以用樹狀數組維護比ak小的 (1/2i+1/2j+…………)的和 。
之后離散化一下就行了。
#pragma GCC optimize(2)
#pragma GCC optimize(3,"Ofast","inline")
#include<bits/stdc++.h>
#define int long long
#define fi first
#define se second
#define pii pair<int,int>
#define IOS ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);
using namespace std
;
const int inf
=2e18+100;
const int maxn
=3e5+100;
const int mod
=998244353;
int a
[maxn
],c
[maxn
];
int n
,mx
;
int qpow(int a
,int b
)
{int ans
=1;while(b
){if(b
&1)ans
=ans
*a
%mod
;a
=a
*a
%mod
;b
=b
>>1;}return ans
%mod
;
}
int lowbit(int x
)
{return x
&(-x
);
}
void update(int x
,int val
)
{while(x
<=mx
){c
[x
]=(c
[x
]+val
)%mod
;x
+=lowbit(x
);}
}
int ask(int x
)
{int ans
=0;while(x
){ans
=(ans
+c
[x
])%mod
;x
-=lowbit(x
);}return ans
%mod
;
}
signed main()
{map
<int,int>mp
;cin
>>n
;for(int i
=1;i
<=n
;i
++){cin
>>a
[i
];mp
[a
[i
]]=1;}for(auto it
:mp
){mp
[it
.fi
]=++mx
;}int ans
=0;for(int i
=1;i
<=n
;i
++){ans
=(ans
+qpow(2,i
-1)*ask(mp
[a
[i
]])%mod
)%mod
;int tp
=qpow(2,i
);update(mp
[a
[i
]],qpow(tp
,mod
-2)%mod
);}cout
<<ans
<<"\n";
}
總結
以上是生活随笔為你收集整理的E - LEQ(树状数组)的全部內容，希望文章能夠幫你解決所遇到的問題。
如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。
