萌新求助,刚学分块,只有10分
查看原帖
萌新求助,刚学分块,只有10分
242012
Perfumer楼主2021/8/5 12:30

除了#2以外全部wa

用分块做的,c记录一段区间内开着的灯的数量,a是每个灯的开关情况,tag是每段区间有没有被开关过

f是用来求每个点的快好的

希望有大佬来帮萌新找找问题

#include <cstdio>
#include <cmath>
#include <algorithm>
using namespace std;
inline int read() {
    int res=0,f=1; char ch=getchar();
    while(ch<'0'||ch>'9') {if(ch=='-') f=-1; ch=getchar();}
    while(ch>='0'&&ch<='9') {res=res*10+ch-'0'; ch=getchar();}
    return res*f;
}
const int MAXN=100005;
int n,m,t;
int a[MAXN],c[MAXN],tag[MAXN];
inline int f(int x) {
    return x%t==0?x/t:x/t+1;
}
signed main() {
    n=read(); m=read();
    t=sqrt(n);
    while(m--) {
        int op=read();
        if(op==0) {
            int l=read(),r=read();
            if(f(l)==f(r)) {
                for(register int i=l;i<=r;++i)
                    a[i]=a[i]^1^tag[f(i)],tag[f(i)]=0;
                c[f(l)]=0;
                for(register int i=(f(l)-1)*t+1;i<=min(f(l)*t,n);++i)
                    c[f(l)]+=a[i];
            } else {
                for(register int i=l;i<=f(l)*t;++i)
                    a[i]=a[i]^1^tag[f(i)],tag[f(i)]=0;
                c[f(l)]=0;
                for(register int i=f(l)*t-t+1;i<=min(f(l)*t,n);++i)
                    c[f(l)]+=a[i];
                for(register int i=f(r)*t-t+1;i<=r;++i)
                    a[i]=a[i]^1^tag[f(i)],tag[f(i)]=0;
                c[f(r)]=0;
                for(register int i=f(r)*t-t+1;i<=min(f(r)*t,n);++i)
                    c[f(r)]+=a[i];
                for(register int i=f(l)+1;i<f(r);++i)
                    c[i]=t-c[i],tag[i]^=1;
            }
        } else if(op==1) {
            int l=read(),r=read();
            int ans=0;
            if(f(l)==f(r)) {
                for(register int i=f(l)*t-t+1;i<=min(f(l)*t,n);++i)
                    ans+=a[i]^tag[f(i)];
            } else {
                for(register int i=l;i<=min(f(l)*t,n);++i)
                    ans+=a[i]^tag[f(i)];
                for(register int i=f(r)*t-t+1;i<=r;++i)
                    ans+=a[i]^tag[f(i)];
                for(register int i=f(l)+1;i<f(r);++i)
                    ans+=c[i];
            }
            printf("%d\n",ans);
        }
    }
    return 0;
}
2021/8/5 12:30
加载中...