【洛谷1267】校门外的树

2018-02-18 12:40:53


现在连基础简单题都一点都写不动了……

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

L <= 10000,N <= 100

刚开始想线段树,怎么都想不出优美的做法
因为一个巨坑的地方是第二个子问题要求已经种过又被拔掉的个数……
最后的想法是开两个线段树,一个记录树的个数,另一个记录有没有被拔过
然后开写之前看了一眼题解,发现了这道题的核心
l*n<=1e6 。。。。。。。。
看数据范围啊看数据范围啊看数据范围啊啊啊
看完数据范围再想题,这种关键的问题都忘了……
行吧行吧直接暴力就行了
暴力能水过就懒得写线段树了,就这样吧
_(:з」∠)_

代码:

#include<iostream>
#include<cstdio>
#include<algorithm>
#include<cstring>
#include<cmath>
using namespace std;
int rd(){int z=0,mk=1;  char ch=getchar();
    while(ch<'0'||ch>'9'){if(ch=='-')mk=-1;  ch=getchar();}
    while(ch>='0'&&ch<='9'){z=(z<<3)+(z<<1)+ch-'0';  ch=getchar();}
    return z*mk;
}
int n,m;
int flg[11000],flg2[11000];
int cnt=0;
int main(){//freopen("ddd.in","r",stdin);
    cin>>n>>m;  int mk,l,r;
    for(int i=0;i<=n;++i)  flg[i]=-1,flg2[i]=false;
    while(m --> 0){
        mk=rd(),l=rd(),r=rd();
        for(int i=l;i<=r;++i){
            if(!mk)  cnt+=(flg2[i] & (flg[i]!=0));
            flg2[i] |= (mk ^ 1);
            if(!flg[i] || !mk)  flg[i]=mk;
        }
    }
    int bwl=0;
    for(int i=0;i<=n;++i)  bwl+=(flg[i]==1);
    cout<<bwl<<endl<<cnt<<endl;
    return 0;
}