luoguP2574 XOR的艺术

思路

01串的区间求和，区间翻转 lazy%20 则不用翻转，lazt%21则要翻转

模板题
代码

#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,a[maxn];

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) {

		e[rt].sum=a[l];

		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();

    FOR(i,1,n) scanf("%1d",&a[i]);

    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;

}
巴特西

luoguP2574 XOR的艺术

思路

代码

最新文章

热门文章
