P11217 分块做法
Little_Fox_Fairy · · 题解
前言：考场当时线段树二分写挂了，
既然是区间加那就果断上 DS 。
记录一个全局的和，每一次乘以 2 ，来找到 youyou 是在哪一轮死亡的，然后利用分块，来找到 youyou 在这一轮中是在哪一次攻击时死亡的。
时间复杂度：
Code:
//在太阳西斜的这个世界里,置身天上之森,等这场战争结束之后,不归之人与望眼欲穿的人们,人人本着正义之名,长存不灭的过去，逐渐消逝的未来,我回来了,纵使日薄西山,即使看不到未来,此时此刻的光辉,盼君勿忘.
#include<bits/stdc++.h>
#define int long long
using namespace std;
namespace fast_IO {
#define IOSIZE 100000
char ibuf[IOSIZE], obuf[IOSIZE], *p1 = ibuf, *p2 = ibuf, *p3 = obuf;
#define getchar() ((p1==p2)and(p2=(p1=ibuf)+fread(ibuf,1,IOSIZE,stdin),p1==p2)?(EOF):(*p1++))
#define putchar(x) ((p3==obuf+IOSIZE)&&(fwrite(obuf,p3-obuf,1,stdout),p3=obuf),*p3++=x)
#define isdigit(ch) (ch>47&&ch<58)
#define isspace(ch) (ch<33)
template<typename T> inline T read() { T s = 0; int w = 1; char ch; while (ch = getchar(), !isdigit(ch) and (ch != EOF)) if (ch == '-') w = -1; if (ch == EOF) return false; while (isdigit(ch)) s = s * 10 + ch - 48, ch = getchar(); return s * w; }
template<typename T> inline bool read(T &s) { s = 0; int w = 1; char ch; while (ch = getchar(), !isdigit(ch) and (ch != EOF)) if (ch == '-') w = -1; if (ch == EOF) return false; while (isdigit(ch)) s = s * 10 + ch - 48, ch = getchar(); return s *= w, true; }
template<typename T> inline void print(T x) { if (x < 0) putchar('-'), x = -x; if (x > 9) print(x / 10); putchar(x % 10 + 48); }
inline bool read(char &s) { while (s = getchar(), isspace(s)); return true; }
inline bool read(char *s) { char ch; while (ch = getchar(), isspace(ch)); if (ch == EOF) return false; while (!isspace(ch)) *s++ = ch, ch = getchar(); *s = '\000'; return true; }
inline void print(char x) { putchar(x); }
inline void print(char *x) { while (*x) putchar(*x++); }
inline void print(const char *x) { for (int i = 0; x[i]; i++) putchar(x[i]); }
inline bool read(std::string& s) { s = ""; char ch; while (ch = getchar(), isspace(ch)); if (ch == EOF) return false; while (!isspace(ch)) s += ch, ch = getchar(); return true; }
inline void print(std::string x) { for (int i = 0, n = x.size(); i < n; i++) putchar(x[i]); }
inline bool read(bool &b) { char ch; while(ch=getchar(), isspace(ch)); b=ch^48; return true; }
inline void print(bool b) { putchar(b+48); }
template<typename T, typename... T1> inline int read(T& a, T1&... other) { return read(a) + read(other...); }
template<typename T, typename... T1> inline void print(T a, T1... other) { print(a), print(other...); }
struct Fast_IO { ~Fast_IO() { fwrite(obuf, p3 - obuf, 1, stdout); } } io;
template<typename T> Fast_IO& operator >> (Fast_IO &io, T &b) { return read(b), io; }
template<typename T> Fast_IO& operator << (Fast_IO &io, T b) { return print(b), io; }
#define cout io
#define cin io
#define endl '\n'
} using namespace fast_IO;
const int N=1e6+10;
const int S=350;
int n,m,e[N];
int q,W,al,all;
int bel[N],L[N],R[N],add[N],loc,sum[N];
inline void init() {
loc=(n-1)/S+1;
for (int i=1;i<=n;i++) bel[i]=(i-1)/S+1;
for (int i=1;i<=loc;i++) L[i]=R[i-1]+1,R[i]=R[i-1]+S;R[loc]=n;
for (int i=1;i<=n;i++) sum[bel[i]]+=e[i];
return ;
}
inline void update(int l,int r,int val,int lc) {
for (int i=l;i<=r;i++) e[i]+=val;
sum[lc]+=(r-l+1)*val;
return ;
}
inline void modify(int l,int r,int val) {
int bll=bel[l],blr=bel[r];
if (bll==blr) {
update(l,r,val,bll);
return ;
}
update(l,R[bll],val,bll);
update(L[blr],r,val,blr);
for (int i=bll+1;i<=blr-1;i++) {
add[i]+=val;
sum[i]+=(R[i]-L[i]+1)*val;
}
return ;
}
signed main() {
cin>>n>>q>>W;
for (int i=1;i<=n;i++) cin>>e[i],al+=e[i];
init();
while (q--) {
int l,r,val;
cin>>l>>r>>val;
modify(l,r,val);
al+=(r-l+1)*val;
all=al;
int x=W,cnt=0,res=0;
while (x>all) { //找到 youyou 是在哪一轮死亡的
x-=all;
cnt++;
res+=n;
all<<=1;
}
int pos,q=(1ll<<cnt);
for (pos=1;pos<=loc;pos++) { //查整块
if (x<=sum[pos]*q) break;
res+=(R[pos]-L[pos]+1);
x-=(sum[pos]*q);
}
for (int j=L[pos];j<=R[pos];j++) { //查散块
if (x<=((e[j]+add[pos])*q)) break;
res++;
x-=((e[j]+add[pos])*q);
}
cout<<res<<endl;
}
return (0-0);
}