Lang:G++
Edit12345678910111213141516171819202122232425262728293031#include<cstdio>#include<cstring>#include<algorithm>using namespace std;const int maxn=100009;const long long MAX=1e9+7;long long sum[maxn*4],mar[maxn*4];void pushup(int o ){sum[o]=sum[o<<1]+sum[o<<1|1];}void pushdown(int o,int m){if(mar[o]){mar[o<<1]+=mar[o];mar[o<<1|1]+=mar[o];sum[o<<1]+=mar[o]*(m-(m>>1));sum[o<<1|1]+=mar[o]*(m>>1);mar[o]=0;}}void build(int l,int r,int o){mar[o]=0;if(l==r){sum[o]=0;return;}int m=(l+r)>>1;