还是线段树,区间更新问题,第一次接触,没太搞透,但感觉不是难理解,明天在草稿上模拟下
code
#include <iostream> #include <fstream> #include <cstdio> #include <algorithm> #include <cstring> #include <string> #include <string.h> #include <vector> #include <bitset> #include <cmath> #include <queue> #include <stack> #include <set> #include <ctime> #include <map> #include <limits> #define LL long long #define Vi vector<int> #define Si set<int> #define readf freopen("input.txt","r",stdin) #define writef freopen("output.txt","w",stdout) #define FF(i,a) for(int i(0); i < (a); i++) #define FD(i,a) for(int i(a); i >= (1); i--) #define FOR(i,a,b) for(int i(a);i <= (b); i++) #define FOD(i,a,b) for(int i(a);i >= (b); i--) #define PD(a) printf("%d",a) #define SET(a,b) memset(a,b,sizeof(a)) #define SD(a) scanf("%d",&(a)) #define LN printf("\n") #define PS printf(" ") #define pb push_back #define lson l , m , rt << 1 #define rson m + 1 , r , rt << 1 | 1 const double pi = acos(-1.0); const int maxn = 500001; const int INF = 99999999; const int dx[]={0,1,0,-1}; const int dy[]={1,0,-1,0}; using namespace std; int col[maxn],sum[maxn]; void PushUP(int rt){ sum[rt]=sum[rt<<1]+sum[rt<<1|1]; } void PushDown(int rt,int m){ if(col[rt]){ //说明已经修改 rt 树是纯色,那么他的子树也要标记为纯色; col[rt<<1]=col[rt<<1|1]=col[rt]; sum[rt<<1]=(m-(m>>1))*col[rt]; //自然sum的值全为col色; sum[rt<<1|1]=(m>>1)*col[rt]; col[rt]=0; //此处还不太明白 } } void build(int l,int r,int rt){ col[rt]=0; if(l==r){ sum[rt]=1; return ; } int m=(l+r)>>1; build(lson); build(rson); PushUP(rt); } void update(int ul,int ur,int c,int l,int r,int rt){ if(ul<=l && ur>=r){ col[rt]=c; sum[rt]=c*(r-l+1); return ; } PushDown(rt,r-l+1); int m=(l+r)>>1; if (ul <= m) update(ul,ur,c,lson); if (ur > m) update(ul,ur,c,rson); PushUP(rt); } int main() { int t; SD(t); FOR(cas,1,t){ int N,M; SD(N);SD(M); build(1,N,1); while(M--){ int ul,ur,color; scanf("%d%d%d",&ul,&ur,&color); update(ul,ur,color,1,N,1); } printf("Case %d: The total value of the hook is %d.\n",cas,sum[1]); } return 0; }