A Simple Problem with Integers

【题目链接】

【题目类型】线段树 成段增减+区间求和

&题解：

线段树 成段增减+区间求和 模板题 这种题真的应该理解并且可以流畅的独立码出来了

【时间复杂度】\(O(nlogn)\)

&代码：

#include 
    
     #include 
     
      #include 
      
       using namespace std;typedef long long ll;const int INF = 0x3f3f3f3f;#define cle(a,val) memset(a,(val),sizeof(a))#define SI(N) scanf("%d",&(N))#define SII(N,M) scanf("%d %d",&(N),&(M))#define SIII(N,M,K) scanf("%d %d %d",&(N),&(M),&(K))#define rep(i,a,b) for(int i=(a);i<=(b);i++)#define red(i,a,b) for(int i=(a);i>=(b);i--)const ll LINF = 0x3f3f3f3f3f3f3f3f;#define PU(x) cout<<#x<
       
         pii;#define fi first#define se second#define pb push_back#define mp make_pair#define sz(x) int(x.size())#define all(x) x.begin(),x.end()const double EPS = 1e-9 ;/*     C o d i n g  S p a c e     */#define lsn b,m,rt<<1#define rsn m+1,e,rt<<1|1const int maxn = (int)1e5 + 9 ;int n,q,a[maxn];ll seg[maxn<<2],si[maxn<<2];void puup(int rt) {    seg[rt]=seg[rt<<1]+seg[rt<<1|1];}void pudo(int len,int rt) {    if(si[rt]) {        si[rt<<1]+=si[rt];        si[rt<<1|1]+=si[rt];        seg[rt<<1]+=si[rt]*(len-len/2);        seg[rt<<1|1]+=si[rt]*(len/2);        si[rt]=0;    }}void build(int b,int e,int rt) {    if(b==e) {        seg[rt]=a[b];        return ;    }    int m=b+e>>1;    build(lsn);    build(rsn);    puup(rt);}ll query(int l,int r,int b,int e,int rt) {    if (l<=b&&e<=r) {        return seg[rt];    }    pudo(e-b+1,rt);    int m=b+e>>1;    ll ans=0;    //小于等于m的全在左儿子  大于m的全在右儿子    //如果需要求的区间[l,r]最左边的那个(也就是l) 小于等于m 那么就一定要往左儿子走    //反之 如果区间[l,r]最右边的那个(也就是r) 大于m 那么就一定要走向右儿子    if (l<=m)        ans+=query(l,r,lsn);    if (m
        
         >1;    if (l<=m)        upda(l,r,xx,lsn);    if (m
         
          >T;while(T--) Solve(); return 0;}