考场上这题我严重降智只拿了(11 pts)。。
感觉自己思维能力和猜结论的能力应当加强，不应该在无关紧要的地方浪费时间。
这题切的人好像不少的样子。。他们太强了
发现总是存在一个(i in [1,n]) 满足(>i)的部分应该全部用优惠券支付，(<i)的部分在保证优惠券数量最大的前提下最大化使用的数量。
（即对于(j<i)使用的优惠券不应超过(a_j mod C)）
(i)使用的优惠券个数可以二分出来。
而且可以发现这个(i)总是取优惠券数目足够的前提下的最大的(i)。
这个可以用线段树维护，我的方法是维护((a,b))表示剩下(a)个优惠券，还可以使用(b)个优惠券。
#include<bits/stdc++.h>
using namespace std;
#define fp(i,l,r) for(register int (i)=(l);i<=(r);++(i))
#define fd(i,l,r) for(register int (i)=(l);i>=(r);--(i))
#define fe(i,u) for(register int (i)=front[(u)];(i);(i)=e[(i)].next)
#define mem(a) memset((a),0,sizeof (a))
#define O(x) cerr<<#x<<':'<<x<<endl
#define int long long
inline int read(){
int x=0,f=1;char ch=getchar();
while(!isdigit(ch)){if(ch=='-')f=-1;ch=getchar();}
while(isdigit(ch))x=x*10+ch-'0',ch=getchar();
return x*f;
}
void wr(int x){
if(x<0)x=-x,putchar('-');
if(x>=10)wr(x/10);
putchar('0'+x%10);
}
const int MAXN=3e5+10;
int n,Q,C,a[MAXN],b[MAXN],c[MAXN];
struct node{
int a,b;
inline node operator+(const node &s)const{
int t=min(a,s.b);
return {a+s.a-t,b+s.b-t};
}
}tr[MAXN<<2];
int sum[MAXN<<2];
#define lson o<<1
#define rson o<<1|1
inline void pushup(int o){
sum[o]=sum[lson]+sum[rson];
tr[o]=tr[lson]+tr[rson];
}
void build(int o,int l,int r){
if(l==r){
tr[o]={a[l],b[l]};sum[o]=c[l];
return;
}
int mid=l+r>>1;
build(lson,l,mid);build(rson,mid+1,r);
pushup(o);
}
int num,p;node tar;
void ask(int o,int l,int r,node t,int s){
if(l==r){
if(t.a+a[l]<s)return;
p=l;num=s;tar=t;
return;
}
int mid=l+r>>1,rsv=s+sum[rson]-c[mid+1];node lsv=t+tr[lson];
if(lsv.a+a[mid+1]<rsv)ask(rson,mid+1,r,lsv,s);
else p=mid+1,num=rsv,tar=lsv,ask(lson,l,mid,t,s+sum[rson]);
}
void upd(int o,int l,int r,int p){
if(l==r){
tr[o]={a[l],b[l]};sum[o]=c[l];
return;
}
int mid=l+r>>1;
if(p<=mid)upd(lson,l,mid,p);
else upd(rson,mid+1,r,p);
pushup(o);
}
struct BIT{
int c[MAXN];
inline void add(int i,int v){
for(;i<=n;i+=i&-i)c[i]+=v;
}
inline int ask(int i){
int res=0;
for(;i;i-=i&-i)res+=c[i];
return res;
}
}T;
inline void solve(){
ask(1,1,n,{0,0},0);int lim=min({c[p],tar.a,(C*(tar.a-num)+c[p])/(C+1)});
/*int l=0,r=min(c[p],tar.a),res;
while(l<=r){
int mid=l+r>>1;
if(tar.a-mid+(c[p]-mid)/C>=num)res=mid,l=mid+1;
else r=mid-1;
}
assert(lim==res);*/
wr(tar.b+c[p]-lim+T.ask(p-1));putchar('
');
}
main(){
n=read();Q=read();C=read();
fp(i,1,n){
c[i]=read();
b[i]=c[i]%C;a[i]=c[i]/C;T.add(i,c[i]-b[i]);
}
build(1,1,n);solve();
while(Q--){
int p=read(),cp=read();
int bp=cp%C,ap=cp/C;T.add(p,-c[p]+b[p]+cp-bp);
a[p]=ap;b[p]=bp;c[p]=cp;upd(1,1,n,p);solve();
}
return 0;
}