题解 P1840 【Color the Axis_NOI导刊2011提高（05）】

· · 题解

遇事不决先分块

我用分块水这道题

这道题很裸，但用线段树来做就有点大材小用了，分块可以说是短小精悍，并且可以维护很多数据，真是居家陆行必备的良器啊

不懂分块 点我领取例题

希望你在分块路上越走越远~ 代码如下：

#include<cstdio>
#include<algorithm>
#include<iostream>
#include<cmath>
#define N 300500
using namespace std;

inline int read() {
    int x = 0,f = 1; char s = getchar();
    while(s < '0' || s > '9') {if(s == '-') f = -1;s = getchar();}
    while(s >= '0' && s <= '9') {x = x * 10 + s - '0';s = getchar();}
    return x * f;
}

int n,m;
int a[N];
int L[N],R[N],tag[N];
int sum[N],lz[N];

inline void Change(int l,int r) {
    if(tag[l] == tag[r]) {
        for(int i = l;i <= r;i ++)
            if(a[i]) a[i] = 0,sum[tag[i]] --;
        return ;
    }
    for(int i = l;i <= R[tag[l]];i ++) 
        if(a[i]) a[i] = 0,sum[tag[l]] --;
    for(int i = tag[l] + 1;i < tag[r];i ++) lz[i] = 1;
    for(int i = L[tag[r]];i <= r;i ++) 
        if(a[i]) a[i] = 0,sum[tag[r]] --;
}

inline int Qurry() {
    int res = 0;
    for(int i = 1;i <= tag[n];i ++)
        if(!lz[i] && sum[i] > 0) 
            res += sum[i];
    return res; 
}

int main() {
    n = read(),m = read();
    int len = sqrt(n);
    for(int i = 1;i <= n;i ++) 
        tag[i] = (i - 1) / len + 1,a[i] = 1;
    for(int i = 1;i <= tag[n];i ++) 
        L[i] = R[i - 1] + 1,R[i] = min(n,L[i] + len - 1); 
    for(int i = 1;i <= tag[n];i ++) 
        sum[i] = R[i] - L[i] + 1;
    for(int i = 1;i <= m;i ++) {
        int l = read(),r = read();
        Change(l,r);
        printf("%d\n",Qurry());
    }
    return 0;
}

谢谢