CodeForces - 339D Xenia and Bit Operations

1877 단어 데이터 구조
CodeForces - 339D Xenia and Bit Operations
제목:
n 과 m 를 지정 하여 2 ^ n 개 수 를 포함 하 는 배열 을 드 립 니 다. m 번 작업 이 있 습 니 다. 매번 작업 할 때마다 p 위치의 수 를 수정 합 니 다. 먼저 두 상 또는 배열 을 반 으로 줄 이 고 두 상이 하거나 배열 을 반 으로 줄 입 니 다. 이 두 가지 작업 을 반복 합 니 다. 배열 에 남 은 요소 가 있 을 때 까지.
m 행 조작
p  v (원래 배열 이 a 라 고 가정)
a [p] 의 값 을 v 로 변경 합 니 다.
첫 번 째 계산 b1 = a [1] | a [2], b2 = a [3] | a [4], b3 = a [5] | a [6], b4 = a [7] | a [8] 
두 번 째 계산 c1 = b1 ^ b2, c2 = b3 ^ b4
제3 차 계산 w = c1 | c2
출력
생각:
라인 트 리 를 유지 합 니 다. 뿌리 노드 는 마지막 요소 의 값 입 니 다.
#include
#include
#include
#include
#include
#include
#include
#include
#include
#include
#include
#include
#include
#include
#define ls rt<<1
#define rs rt<<1|1
using namespace std;
typedef long long ll;
const int maxn = 1e6+10;
int a[maxn],sum[maxn];
void pushup(int rt,int f)  //     n+1                n 
{
    if(f==1)    
        sum[rt] = sum[ls]|sum[rs];
    else
        sum[rt] = sum[ls]^sum[rs];
}
void build(int l,int r,int rt,int f)
{
    if(l==r)
    {
        sum[rt] = a[l];
        return ;
    }
    int m = (l+r)>>1;
    build(l,m,ls,1-f);
    build(m+1,r,rs,1-f);
    pushup(rt,f);
}
void update(int p,int c,int l,int r,int rt,int f)
{
    if(l==r)
    {
        sum[rt] = c;
        return ;
    }
    int m = (l+r)>>1;
    if(p<=m)
        update(p,c,l,m,ls,1-f);
    if(p>m)
        update(p,c,m+1,r,rs,1-f);
    pushup(rt,f);
}
int main()
{
    int n,m;
    int k;
    scanf("%d%d",&n,&m);
    k = (1<

좋은 웹페이지 즐겨찾기