Codeforce 915E(线段树动态开点)

╰+攻爆jí腚メ 2021-11-01 07:10 365阅读 0赞

日常安利：[https://blog.csdn.net/stay\_accept/article/details/79210918][https_blog.csdn.net_stay_accept_article_details_79210918]  
[![知识共享许可协议][80x15.png]][80x15.png 1]  
本作品采用[知识共享署名-相同方式共享 4.0 国际许可协议][80x15.png 1]进行许可。  
This year Alex has finished school, and now he is a first-year student of Berland State University. For him it was a total surprise that even though he studies programming, he still has to attend physical education lessons. The end of the term is very soon, but, unfortunately, Alex still hasn’t attended a single lesson!  
Since Alex doesn’t want to get expelled, he wants to know the number of working days left until the end of the term, so he can attend physical education lessons during these days. But in BSU calculating the number of working days is a complicated matter:  
There are n days left before the end of the term (numbered from 1 to n), and initially all of them are working days. Then the university staff sequentially publishes q orders, one after another. Each order is characterised by three numbers l, r and k:  
If k = 1, then all days from l to r (inclusive) become non-working days. If some of these days are made working days by some previous order, then these days still become non-working days;  
If k = 2, then all days from l to r (inclusive) become working days. If some of these days are made non-working days by some previous order, then these days still become working days.  
Help Alex to determine the number of working days left after each order!  
Input  
The first line contains one integer n, and the second line — one integer q (1 ≤ n ≤ 109, 1 ≤ q ≤ 3·105) — the number of days left before the end of the term, and the number of orders, respectively.  
Then q lines follow, i-th line containing three integers li, ri and ki representing i-th order (1 ≤ li ≤ ri ≤ n, 1 ≤ ki ≤ 2).  
Output  
Print q integers. i-th of them must be equal to the number of working days left until the end of the term after the first i orders are published.  
Example  
Input  
4  
6  
1 2 1  
3 4 1  
2 3 2  
1 3 2  
2 4 1  
1 4 2  
Output  
2  
0  
2  
3  
1  
4  
分析：  
这个题的n范围虽然很大，但是q不是很大。 所以可以用离散化在建线段树的方法。在结点里面维护一个区间和即可。

不过，正好在学动态开点。所以这个题就用了一下动态开点+laze标记。  
laze标记，是指表示该结点曾经被修改，但是其子结点未被更新。  
同时动态开点无非就是把2*id 和2*id+1作为子孩子，现在改用变量来记录其子结点。

#include"stdio.h"
    #include"string.h"
    #include"algorithm"
    using namespace std;
    
    int n,q;
    int laze[5 * 3000100],sum[5 * 3000100],lson[5 * 3000100],rson[5 * 3000100];
    int top;
    
    void push_down(int id,int l,int r)
    {
        if(laze[id] == -1)
            return;
        if(lson[id] == 0)
            lson[id] = ++ top;
        if(rson[id] == 0)
            rson[id] = ++ top;
        int mid = (l + r) >> 1;
        sum[lson[id]] = (mid - l + 1) * laze[id];
        laze[lson[id]] = laze[id];
        sum[rson[id]] = (r - (mid + 1) + 1) * laze[id];
        laze[rson[id]] = laze[id];
        laze[id] = -1;
    }
    
    void Update(int id,int L,int R,int l,int r,int val)
    {
      //  printf("id = %d L = %d R = %d l = %d r = %d val = %d\n",id,L,R,l,r,val);
        if(l <= L && r >= R)
        {
            laze[id] = val;
            sum[id] = (R - L + 1) * val;
            return ;
        }
        push_down(id,L,R);
        int mid = (L + R) >> 1;
        if(l <= mid)
        {
            if(lson[id] == 0)//这里注意一下，不能把Update也写在if里面
            {
                lson[id] = ++ top;
            }
            Update(lson[id],L,mid,l,r,val);
        }
        if(r > mid)
        {
            if(rson[id] == 0)
            {
                rson[id] = ++ top;
            }
            Update(rson[id],mid + 1,R,l,r,val);
        }
        sum[id] = sum[lson[id]] + sum[rson[id]];
    }
    
    int main()
    {
        scanf("%d",&n);
        scanf("%d",&q);
        for(int i = 1; i <= 40 * q; i ++)
            laze[i] = -1;
        for(int i = 1; i <= q; i ++)
        {
            int l,r,op;
            scanf("%d%d%d",&l,&r,&op);
            if(op == 2)
                op = 0;
            Update(0,1,n,l,r,op);
            printf("%d\n",n - sum[0]);
        }
    }

[https_blog.csdn.net_stay_accept_article_details_79210918]: https://blog.csdn.net/stay_accept/article/details/79210918
[80x15.png]: https://i.creativecommons.org/l/by-sa/4.0/80x15.png
[80x15.png 1]: http://creativecommons.org/licenses/by-sa/4.0/