首页 > 代码库 > Codeforces Round #254 DZY Loves Colors

Codeforces Round #254 DZY Loves Colors

2024-07-11 00:38:13   219人阅读

题意：输入n, m ; 有n给位置， 初始时第i个位置的color为i, colorfulness为0。

     有m次操作，一种是把成段的区域color更新为x， 对于更新的区域，每个位置（令第i个位置未更新前颜色为color[i]）的colorfulness增加|color[i] -x|;

     另一种操作是询问一段区间[L,R]输出该区间的colorfulness总和。

 

  1 #include <iostream>  2 #include <cstdio>  3 #include <cstring>  4 #include <algorithm>  5 #include <cmath>  6 using namespace std;  7 #define lson l,m,rt<<1  8 #define rson m+1,r,rt<<1|1  9 typedef long long ll; 10 const int N  = 111111; 11 int n, m, color[N<<2]; 12 ll delta[N<<2], sum[N<<2]; 13  14 void build(int l, int r, int rt) 15 { 16     color[rt] = delta[rt] = sum[rt] = 0; 17     if(l==r){ 18         color[rt] = l;//第i个位置颜色为i 19         return ; 20     } 21     int m = (l+r)>>1; 22     build(lson); 23     build(rson); 24 } 25  26 void Up(int l, int r, int rt) 27 { 28     sum[rt] = sum[rt<<1] + sum[rt<<1|1] + 1LL*delta[rt]*(r-l+1); 29 } 30  31 void Down(int rt) 32 { 33     if(color[rt]>0) 34     { 35         color[rt<<1] = color[rt<<1|1] = color[rt]; 36         color[rt] = 0; 37     } 38 } 39  40 void Check(int x, int l, int r,int rt) 41 { 42     if(color[rt]>0) 43     { 44         delta[rt] += abs(x - color[rt]); 45         sum[rt] +=  1LL *abs(x - color[rt]) * (r-l+1); 46     } 47     else 48     { 49         int m = (l+r)>>1; 50         Check(x,lson); Check(x,rson); 51         Up(l, r, rt); 52     } 53     color[rt] = x; 54 } 55  56 void update(int L, int R, int x, int l, int r, int rt) 57 { 58     if(L<=l&&R>=r){ 59         Check(x, l, r, rt); 60         return ; 61     } 62     Down(rt); 63     int m = (l+r)>>1; 64     if(L<=m) update(L, R, x, lson); 65     if(R>m) update(L, R, x, rson); 66     Up(l, r, rt); 67 } 68  69 ll query(int L, int R, int l, int r,int rt) 70 { 71     if(L<=l&&R>=r) return sum[rt] ; 72     int m = (l+r)>>1; 73     ll ans = 0; 74     if(R<=m) 75         ans += query(L, R, lson) + 1LL * delta[rt] *(R-L+1); 76     else if(L>m) 77         ans += query(L, R, rson) + 1LL * delta[rt] * (R-L+1); 78     else 79         ans += query(L, m , lson) + query(m+1, R, rson) + 1LL * delta[rt] * (R-L+1); 80     return ans; 81 } 82  83 int main() 84 { 85 //    freopen("in.txt", "r", stdin); 86     while(scanf("%d%d", &n, &m)>0) 87     { 88         build(1, n, 1); 89         int type, l, r, x; 90         while(m--) 91         { 92             scanf("%d%d%d", &type, &l, &r); 93             if(type == 1) 94             { 95                 scanf("%d", &x); 96                 update(l, r, x, 1, n, 1); 97             } 98             else 99                 printf("%I64d\n",query(l, r, 1, n, 1));100         }101     }102     return 0;103 }

 


联系
我们