如何在税局网站上做税种认定,wordpress后台入口,店铺营业执照在哪个网站做年审,云浮疫控动态正题
题目链接:https://www.luogu.com.cn/problem/P6834?contestId34123 题目大意 nnn个点#xff0c;每个点i(i≠1)i(i\neq 1)i(i1)随机连接[i−k,i−1][i-k,i-1][i−k,i−1]中的一个点。对于每个点有一个权值aia_iai。每次可以选择一个全部都是正权值的连通块里所有…正题
题目链接:https://www.luogu.com.cn/problem/P6834?contestId34123 题目大意
nnn个点每个点i(i≠1)i(i\neq 1)i(i1)随机连接[i−k,i−1][i-k,i-1][i−k,i−1]中的一个点。对于每个点有一个权值aia_iai。每次可以选择一个全部都是正权值的连通块里所有权值减一求最优期望次数。 解题思路
考虑每个点的贡献对于一个节点xxx和它的父节点fafafa显然根据铺设道路那题的做法这个点的贡献就是max{ax−afa,0}max\{a_x-a_{fa},0\}max{ax−afa,0}
所以我们需要维护一个数据结构可以查询比axa_xax小的数的和支持插入删除。显然离散化之后用树状数组即可。
时间复杂度O(nlogn)O(n\log n)O(nlogn) codecodecode
#includecstdio
#includecstring
#includealgorithm
#define lowbit(x) (x-x)
#define ll long long
using namespace std;
const ll N1e610,XJQ998244353;
ll n,k,num,answer,cnt;
ll inv[N],a[N],b[N],t[N],z[N];
ll power(ll x,ll b){ll ans1;while(b){if(b1)ansans*x%XJQ;xx*x%XJQ;b1;}return ans;
}
void Change(ll x,ll val,ll flag){while(xcnt){t[x](t[x]val)%XJQ;z[x]z[x]flag;xlowbit(x);}return;
}
ll Ask(ll x){ll ans0;num0;while(x){numnumz[x];ans(anst[x])%XJQ;x-lowbit(x);}return ans;
}
int main()
{scanf(%lld%lld,n,k);inv[1]1;for(ll i2;ik;i)inv[i]XJQ-XJQ/i*inv[XJQ%i]%XJQ;for(ll i1;in;i)scanf(%lld,a[i]),b[cnt]a[i];sort(b1,b1cnt);cntunique(b1,b1cnt)-b-1;ll l1,sum0;answera[1];for(ll i1;in;i){while(lnli-k){ll ylower_bound(b1,b1cnt,a[l])-b;Change(y,-a[l],-1);l;}ll xlower_bound(b1,b1cnt,a[i])-b;ll wAsk(x),ans0;ans(num*a[i]%XJQ-wXJQ)%XJQ;answer(answerans*inv[min(i-1,k)]%XJQ)%XJQ;Change(x,a[i],1);}printf(%lld,answer);
}
