WA help
查看原帖
WA help
1296826
lcfollower楼主2025/8/29 13:04

甚至不会动态开点模板,求调。

#include <bits/stdc++.h>
using namespace std;

#define int unsigned long long
#define up(i,x,y) for(register int i=x;i<=y;++i)
#define dn(i,x,y) for(register int i=x;i>=y;--i)

using namespace std;

inline int read(){int x=0;bool f=0;char ch=getchar();while(!isdigit(ch)){f|=(ch=='-');ch=getchar();}while(isdigit(ch))x=(x<<1)+(x<<3)+(ch^48),ch=getchar();return (f?-x:x);}
inline void write(int x){if(x<0)putchar('-'),x=-x;if(x>9)write(x/10);putchar(x%10|48);}
inline void writeln(int x){write(x),putchar('\n');}
inline void writesp(int x){write(x),putchar(' ');}

const int N = 1e5 + 10;
int n ,Q ;

struct SGT{int sum ,lazy;}tr[N * 31];
int lc[N * 31] ,rc[N * 31];
int idx;

inline void pushup(int u){
  tr[u].sum = (lc[u] != 0) * tr[lc[u]].sum + (rc[u] != 0) * tr[rc[u]].sum;
} inline void pushdown(int u ,int l ,int r){
    int mid = ((l + r) >> 1);
  if(tr[u].lazy){
    if(!lc[u]) lc[u] = ++ idx;
    if(!rc[u]) rc[u] = ++ idx;
    tr[lc[u]].lazy += tr[u].lazy;
	tr[rc[u]].lazy += tr[u].lazy;
	tr[lc[u]].sum += (mid - l + 1) * tr[u].lazy;
	tr[rc[u]].sum += (r - mid) * tr[u].lazy;
	tr[u].lazy = 0; 
  }
} inline int update(int u,int l ,int r ,int L,int R,int v){
  if(!u) u = ++ idx;
  if(l >= L && r <= R){
  	tr[u].sum += (r - l + 1) * v;
  	tr[u].lazy += v;
  	return u;
  }
  pushdown(u ,l ,r);
  int mid = ((l + r) >> 1);
  if(L <= mid) lc[u] = update(lc[u] ,l ,mid ,L ,R ,v);
  if(mid < R) rc[u] = update(rc[u],mid + 1 ,r , L , R ,v);
  pushup(u);
    return u;
} inline int query(int u,int l ,int r ,int L,int R){
  if(!u) return 0;
  if(l >= L && r <= R) return tr[u].sum;
  pushdown(u ,l ,r);
  int mid = ((l + r) >> 1) ,val = 0;
  if(L <= mid) val += query(lc[u] ,l ,mid ,L , R);
  if(mid < R) val += query(rc[u], mid + 1 ,r ,L ,R);
  return val;
}signed main(){
  n = read() , Q = read();
  while(Q --){
    int op = read() , L = read() , R = read();
    if(op == 1) {int v = read();update(1 ,1 ,n ,L ,R ,v);}
    if(op == 2) writeln(query(1 ,1 ,n ,L ,R) + (L + R) * (R - L + 1) / 2); 
  }
  return 0;
}
2025/8/29 13:04
加载中...