P3870 [TJOI2009]开关

思路

代码

#include <iostream>

#include <vector>

#include <cstdio>

#include <cstring>

#include <algorithm>

#include <queue>

#include <cmath>

#define ls rt<<1

#define rs rt<<1|1

#define ll long long

#define FOR(i,a,b) for(int i=a;i<=b;++i)

using namespace std;

const int maxn = 2e5 + 7;

int read() {

    int x = 0, f = 1; char s = getchar();

    for (; s < '0' || s > '9'; s = getchar()) if (s == '-') f = -1;

    for (; s >= '0' && s <= '9'; s = getchar()) x = x * 10 + s - '0';

    return x * f;

}

int n, m;

struct node{

    int l,r,size,sum,lazy;

}e[maxn<<2];

void pushup(int rt) {

    e[rt].sum=e[ls].sum+e[rs].sum;

}

void pushdown(int rt) {

    if(e[rt].lazy%2) {

        e[ls].lazy++;

        e[rs].lazy++;

        e[ls].sum=e[ls].size-e[ls].sum;

        e[rs].sum=e[rs].size-e[rs].sum;

        e[rt].lazy=0;

    }

}

void build(int l,int r,int rt) {

    e[rt].l=l,e[rt].r=r,e[rt].size=r-l+1;

    if(l==r) return;

    int mid=(l+r)>>1;

    build(l,mid,ls);

    build(mid+1,r,rs);

    pushup(rt);

}

void modfity(int L,int R,int rt) {

    if(L<=e[rt].l&&e[rt].r<=R) {

        e[rt].sum=e[rt].size-e[rt].sum;

        e[rt].lazy++;

        return;

    }

    pushdown(rt);

    int mid=(e[rt].l+e[rt].r)>>1;

    if(L<=mid) modfity(L,R,ls);

    if(R>mid) modfity(L,R,rs);

    pushup(rt);

}

int query(int L,int R,int rt) {

    if(L<=e[rt].l&&e[rt].r<=R) {

        return e[rt].sum;

    }

    pushdown(rt);

    int mid=(e[rt].l+e[rt].r)>>1,ans=0;

    if(L<=mid) ans+=query(L,R,ls);

    if(R>mid) ans+=query(L,R,rs);

    return ans;

}

int main() {

    n=read(),m=read();

    build(1,n,1);

    FOR(i,1,m) {

    	int p=read(),x=read(),y=read();

    	if(p) {

    		printf("%d\n",query(x,y,1));

    	} else {

    		modfity(x,y,1);

    	}

    }

    return 0;

}
巴特西

P3870 [TJOI2009]开关

思路

代码

最新文章

热门文章
