로 곡 P2574 - XOR 의 예술

1948 단어 데이터 구조
제목 은 말 하지 않 겠 습 니 다. 중국어 의 간단 한 제목 이기 때문에 분명 한 선분 트 리 입 니 다. lazy 배열 로 구간 이 몇 번 수정 되 었 는 지 유지 하고 매번 구간 이 수정 되면 구간 중 1 의 개 수 는 구간 길이 로 원래 구간 중 1 의 개 수 를 빼 고 이 문 제 를 해결 할 수 있 습 니 다.
낙 곡 의 평 점 에 문제 가 있 는 것 같 습 니 다. 이것 은 분명 간단 한 문제 인 데 왜 이것 이 파란색 문제 일 수 있 습 니까?컨디션 이 너무 안 좋아 서 문 제 를 풀 거 야!!!
마지막, 코드:
#include
using namespace std;
string str;
const int maxn=2e5+100;
int ans;
int tree[maxn<<2];
int lazy[maxn<<2];
void push_up(int tp,int x)
{
    tree[x]=tree[tp]+tree[tp+1];
}
void push_down(int tp,int x,int l,int mid,int r)
{
    lazy[tp]^=lazy[x];
    lazy[tp+1]^=lazy[x];
    lazy[x]=0;
    tree[tp]=(mid-l+1)-tree[tp];
    tree[tp+1]=(r-mid)-tree[tp+1];
}
void build(int l,int r,int x)
{
    if(l==r)
    {
        if(str[l-1]=='1')
            tree[x]=1;
        return ;
    }
    int tp=x<<1;
    int mid=l+r>>1;
    build(l,mid,tp);
    build(mid+1,r,tp+1);
    push_up(tp,x);
}
void update(int l,int r,int x,int L,int R)
{
    if(l>R||r=r)
    {
        lazy[x]^=1;
        tree[x]=(r-l+1-tree[x]);
        return ;
    }
    int tp=x<<1;
    int mid=l+r>>1;
    if(lazy[x])
    {
        push_down(tp,x,l,mid,r);
    }
    update(l,mid,tp,L,R);
    update(mid+1,r,tp+1,L,R);
    push_up(tp,x);
}
void query(int l,int r,int x,int L,int R)
{
    if(l>R||r=r)
    {
        ans+=tree[x];
        return ;
    }
    int tp=x<<1;
    int mid=l+r>>1;
    if(lazy[x])
    {
        push_down(tp,x,l,mid,r);
    }
    query(l,mid,tp,L,R);
    query(mid+1,r,tp+1,L,R);
    push_up(tp,x);
}
int main()
{
    int n,m;
    cin>>n>>m;
    cin>>str;
    build(1,n,1);
    int opt,l,r;
    for(int i=0;i>opt>>l>>r;
        if(opt)
        {
            ans=0;
            query(1,n,1,l,r);
            cout<

좋은 웹페이지 즐겨찾기