洛谷 P1276 校门外的树（增强版）

题目描述

校门外马路上本来从编号0到L，每一编号的位置都有1棵树。有砍树者每次从编号A到B处连续砍掉每1棵树，就连树苗也不放过（记 0 A B ，含A和B）；幸运的是还有植树者每次从编号C到D 中凡是空穴（树被砍且还没种上树苗或树苗又被砍掉）的地方都补种上树苗（记 1 C D，含C和D）；问最终校门外留下的树苗多少棵？植树者种上又被砍掉的树苗有多少棵？

输入输出格式

输入格式：

第一行L和N,表示校园外原来有L+1棵树，并有N次砍树或种树的操作。

以下N行，砍树或植树的标记和范围，每行3个整数。

L（1 <= L <= 10000）和 N（1 <= N <= 100）

输出格式：

共两行。第1行校门外留下的树苗数目，第2行种上又被拔掉的树苗数目。

输入输出样例

输入样例#1：

输出样例#1：

3

2

说明

【数据范围】

对于100%的数据0≤n,l≤10^9

码了一上午线段树没码出AC 就写了个模拟

#include<cstdio>

int l,n,a,b,c,xz,sy;

int t[];

int main(){

    scanf("%d%d",&l,&n);

    for(int i=;i<=l;i++) t[i]=;

    while(n--){

        scanf("%d%d%d",&a,&b,&c);

        if(a){

            for(int i=b;i<=c;i++)

            if(!t[i]) t[i]=;

        }

        else{

            for(int i=b;i<=c;i++){

                if(t[i]==) ++xz;

                t[i]=;

            }

        }

    }

    for(int i=;i<=l;i++)

    if(t[i]==) ++sy;

    printf("%d\n%d\n",sy,xz);

    return ;

}

巴特西

洛谷 P1276 校门外的树（增强版）

题目描述

输入输出格式

输入输出样例

说明

最新文章

热门文章