【LOJ】#2016. 「SCOI2016」美味

题解

做了一下SCOI2015，于是决定搬运SCOI2016= v =

如果没有加法，我们可以向左向右节点查找

每个总权值是2^18 - 1，然后左右分，那么每次是一个完整的节点

如果有了加法，那么我们如果希望有数满足某一位是1或者0，是一段取值的区间，我们要保证这个区间的左右端点减少x后这个区间里还有值

我们可以通过一次\(\log n\)的操作完成这个东西

那么我们二分的话，复杂度也是\(\log n\)的

所以总复杂度就是\(O(m \log^2 n)\)的

代码

#include <bits/stdc++.h>

//#define ivorysi

#define MAXN 200005

typedef long long int64;

typedef unsigned int u32;

using namespace std;

const int MOD = 1000000007;

int n,m;

int a[MAXN];

struct node {

    int lc,rc;

    int size;

}tr[MAXN * 20];

int rt[MAXN],nodecnt;

int MAXVAL = 100000;

void add(const int &x,int &y,int l,int r,int pos) {

    y = ++nodecnt;

    tr[y] = tr[x];

    tr[y].size++;

    if(l == r)return;

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

    if(pos <= mid) add(tr[x].lc,tr[y].lc,l,mid,pos);

    else add(tr[x].rc,tr[y].rc,mid + 1,r,pos);

}

int query(const int &u,int l,int r,int ql,int qr) {

    if(l == ql && r == qr) return tr[u].size;

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

    if(qr <= mid) return query(tr[u].lc,l,mid,ql,qr);

    else if(ql > mid) return query(tr[u].rc,mid + 1,r,ql,qr);

    else {

	return query(tr[u].lc,l,mid,ql,mid) + query(tr[u].rc,mid + 1,r,mid + 1,qr);

    }

}

void Init() {

    scanf("%d%d",&n,&m);

    for(int i = 1 ; i <= n ; ++i) {

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

	add(rt[i - 1],rt[i],0,MAXVAL,a[i]);

    }

}

int getsize(int L,int R,int ql,int qr) {

    if(ql < 0) ql = 0;

    qr = min(qr,MAXVAL);

    if(qr < ql) return 0 ;

    return query(rt[R],0,MAXVAL,ql,qr) - query(rt[L - 1],0,MAXVAL,ql,qr);

}

int Binary(int b,int x,int Lrt,int Rrt) {

    int L = 0,R = (1 << 18) - 1;

    int NUM = 0;

    for(int i = 17 ; i >= 0 ; --i) {

	if(b >> i & 1) {

	    int T = NUM + (1 << i) - 1;

	    if(getsize(Lrt,Rrt,L - x,T - x) > 0) {

		R = T;

	    }

	    else {

		L = T + 1;

		NUM += (1 << i);

	    }

	}

	else {

	    int T = NUM + (1 << i);

	    if(getsize(Lrt,Rrt,T - x,R - x) > 0) {

		NUM += (1 << i);

		L = T;

	    }

	    else R = T - 1;

	}

    }

    return b ^ NUM;

}

void Solve() {

    Init();

    int b,x,l,r;

    while(m--) {

	scanf("%d%d%d%d",&b,&x,&l,&r);

	printf("%d\n",Binary(b,x,l,r));

    }

}

int main() {

#ifdef ivorysi

    freopen("food1.in","r",stdin);

#endif

    Solve();

}

巴特西

【LOJ】#2016. 「SCOI2016」美味

题解

代码

最新文章

热门文章