正題

題目鏈接:https://www.luogu.com.cn/problem/P3527

---

題目大意

$m$個格子形成的環(huán)，有$n$個集合，第$i$個格子屬于第$o_i$個集合，$k$次讓環(huán)上一段的格子加上一個權(quán)值。

對于每個$i$求出第$i$個集合在多少次的時候它集合中的所有格子權(quán)值和大于$p_i$

---

解題思路

單個的時候可以二分做，多個的時候就一起二分做。

對于每次二分的區(qū)域$[L,R]$就把$[L,mid]$操作給做了，然后判斷目前集合內(nèi)滿足條件的丟到左邊，不滿足的丟到右邊繼續(xù)分治下去。

用樹狀數(shù)組維護(hù)區(qū)間和就好統(tǒng)計了，像$CDQ$分治一樣注意做完左邊不需要清空影響，留到右邊作為信息。

環(huán)形的話一個操作拆成兩個就好了。

時間復(fù)雜度$O(n{\log }^{2}n)$

---

$code$

#include<cstdio> #include<cstring> #include<algorithm> #include<vector> #define lowbit(x) (x&-x) #define ll long long using namespace std; const ll N=3e5+10; struct node{ll l,r,w; }q[N]; ll n,m,k,p[N],p1[N],p2[N],t[N],ans[N],lim[N]; vector<ll> v[N]; void Change(ll x,ll val){while(x<=m){t[x]+=val;x+=lowbit(x);}return; } ll Ask(ll x){ll ans=0;while(x){ans+=t[x];x-=lowbit(x);}return ans; } void solve(ll L,ll R,ll l,ll r){if(L==R){for(ll i=l;i<=r;i++)ans[p[i]]=L;ll i=L;if(q[i].l<=q[i].r)Change(q[i].l,q[i].w),Change(q[i].r+1,-q[i].w);elseChange(q[i].l,q[i].w),Change(1,q[i].w),Change(q[i].r+1,-q[i].w);return;}ll mid=(L+R)>>1;for(ll i=L;i<=mid;i++){if(q[i].l<=q[i].r)Change(q[i].l,q[i].w),Change(q[i].r+1,-q[i].w);elseChange(q[i].l,q[i].w),Change(1,q[i].w),Change(q[i].r+1,-q[i].w);}ll cnt1=0,cnt2=0;for(ll i=l;i<=r;i++){ll x=p[i],w=0;for(ll j=0;j<v[x].size();j++){w+=Ask(v[x][j]);if(w>=lim[x])break;}if(w>=lim[x])p1[++cnt1]=x;else p2[++cnt2]=x;}ll cnt=l-1;for(ll i=1;i<=cnt1;i++)p[++cnt]=p1[i];for(ll i=1;i<=cnt2;i++)p[++cnt]=p2[i];for(ll i=L;i<=mid;i++){if(q[i].l<=q[i].r)Change(q[i].l,-q[i].w),Change(q[i].r+1,q[i].w);elseChange(q[i].l,-q[i].w),Change(1,-q[i].w),Change(q[i].r+1,q[i].w);}solve(L,mid,l,r-cnt2);solve(mid+1,R,l+cnt1,r);return; } signed main() {scanf("%lld%lld",&n,&m);for(ll i=1;i<=m;i++){ll x;scanf("%lld",&x);v[x].push_back(i);}for(ll i=1;i<=n;i++)scanf("%lld",&lim[i]),p[i]=i;scanf("%lld",&k);for(ll i=1;i<=k;i++)scanf("%lld%lld%lld",&q[i].l,&q[i].r,&q[i].w);q[++k]=(node){1,n,(ll )1e9+7};solve(1,k,1,n);for(ll i=1;i<=n;i++){if(ans[i]<k)printf("%lld\n",ans[i]);else printf("NIE\n");}return 0; }

總結(jié)

以上是生活随笔為你收集整理的P3527-[POI2011]MET-Meteors【整体二分,树状数组】的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網(wǎng)站內(nèi)容還不錯，歡迎將生活随笔推薦給好友。