hack

hack @__ex

这个人太菜了，分块都写不对，还 AC 了，我要制裁他

评测记录

他的代码

#include <bits/stdc++.h>
typedef long long ll;
using namespace std;
template<typename T>inline T read(){
    T a=0;bool s=0;
    char ch=getchar();
    while(ch>'9' || ch<'0'){
        if(ch=='-')s^=1;
        ch=getchar();
    }
    while(ch>='0' && ch<='9'){
        a=(a<<3)+(a<<1)+(ch^48);
        ch=getchar();
    }
    return s?-a:a;
}
const int mn=1e7+10;
bool vis[mn];
int n,m,sqr,tot,a[mn],l[mn],r[mn],bel[mn],tag[mn];
inline void init(){
    sqr=sqrt(n);
    tot=n/sqr;
    if(n%sqr)tot++;
    for(int i=1;i<=tot;i++)
        l[i]=(i-1)*sqr+1,r[i]=i*sqr;
    r[tot]=n;
    for(int i=1;i<=n;i++)
        bel[i]=(i-1)/sqr+1;
}
inline void cg(int L,int R,int num){
    int lx=bel[L],rx=bel[R];
    if(lx==rx){
        if(tag[lx]){
            for(int i=l[lx];i<=r[lx];i++)
                a[i]=tag[lx];
            tag[lx]=0;
        }
        for(int i=L;i<=R;i++)
            a[i]=num;
        return;
    }
    if(tag[lx]){
        for(int i=l[lx];i<L;i++)
            a[i]=tag[lx];
        tag[lx]=0;
    }
    if(tag[rx]){
        for(int i=R+1;i<=r[rx];i++)
            a[i]=tag[rx];
    }
    for(int i=L;i<=r[lx];i++)
        a[i]=num;
    for(int i=lx+1;i<rx;i++)
        tag[i]=num;
    for(int i=l[rx];i<=R;i++)
        a[i]=num;
}
int main(){
    // freopen("P3740.in","r",stdin);
    // freopen("P3740.out","w",stdout);
    n=read<int>();m=read<int>();
    init();
    for(int i=1;i<=m;i++){
        int a=read<int>(),b=read<int>();
        cg(a,b,i);
    }
    int ans=0;
    for(int i=1;i<=n;i++){
        if(tag[bel[i]]){
            if(!vis[tag[bel[i]]])
                ans++,vis[tag[bel[i]]]=1;
        }
        else{
            if(a[i] && !vis[a[i]])
                ans++,vis[a[i]]=1;
        }
    }
    printf("%d\n",ans);
    // while(1)getchar();
    return 0;
}

hack 数据

1000000 100
16728 43612
11828 15659
27879 52164
88 9756
2069 24808
28984 58455
2902 13997
2578 4526
1 18746
1544 15662
6750 24522
23760 42425
14848 23562
26030 50205
17493 21740
9887 31911
3451 5381
9175 20551
17237 37982
17262 25882
3807 34260
6487 16012
24510 36836
12177 31977
5660 18708
7841 31870
32434 36792
2623 11302
21798 21851
22096 29547
16536 30093
10260 32792
32376 45115
1953 21335
12186 24460
13712 26178
31628 33080
2294 15872
32295 43867
27030 51036
13156 34001
14932 20953
21873 22801
18413 33365
24836 57214
4070 5393
13296 20036
29634 51031
31222 53422
11384 16523
23517 30973
4644 21188
9412 17860
3069 27364
20920 21183
15495 34867
16258 19748
15882 37746
27330 50053
834 28021
30274 59682
12376 36159
27524 58562
17 1428
27037 49932
2374 18963
13894 42080
30868 35792
25905 48683
4692 34152
2457 18370
4301 36512
9757 27324
12969 20341
20174 52931
3494 27320
12679 22774
31118 63525
30845 46775
10089 42494
15126 19464
14577 23070
28927 40295
27718 43669
7033 19738
12259 34236
6387 17429
13009 25044
22238 40520
17690 19476
21949 29310
7297 12108
13179 36267
20848 43507
12290 14803
10290 19398
24585 43090
31330 37597
557 6079
21668 32836

正确输出：15

他的输出：14