CSAcademy Round #32 : F. Light Count

一時期SRMでもこんな問題でたなぁ。
https://csacademy.com/contest/round-32/task/light-count/

問題

1～Nの番号の電球が並んでいる。
以下のクエリM個に答えよ。

• k番の電球のオンオフを切り替える。
• [L,R]番の範囲の電球でオンのものの数を数え上げる。

ただしN≦5*10^7、M≦2*10^7の制限に対しメモリは12MBしか使えない。

解法

オンオフは1電球1bitで管理すればメモリに収まる。
数え上げはBITで行えばよいが、普通に行うとMLEする。
以下のコードでは電球1024個ごとにカウンタを持ち、BITを用いた。

カウンタをまとめるサイズをBとすると、1クエリO(B+log(N/B))で処理でき何とか間に合う。

unsigned long long B[50000000/64+1];
template<class V, int ME> class BIT {
public:
	V bit[1<<ME];
	V operator()(int e) {V s=0;e++;while(e) s+=bit[e-1],e-=e&-e; return s;}
	V add(int e,V v) { e++; while(e<=1<<ME) bit[e-1]+=v,e+=e&-e;}
};
BIT<int,17> bt;


struct RandGen {
	int x, y, z;

	int nextInt() {
		int t = x ^ (x << 11);
		x = y;
		y = z;
		z ^= (z >> 19) ^ t ^ (t >> 8);
		return z;
	}

	int random(int N) {
		return nextInt() % N;
	}
};

void init(int N, int M) {
}

void flipPosition(int poz) {
	unsigned long long m=1ULL<<(poz&63);
	if(B[poz>>6] & m) {
		bt.add((poz>>10)+1,-1);
	}
	else {
		bt.add((poz>>10)+1,+1);
	}
	B[poz>>6] ^= m;
}

int getCount(int st, int fn) {
	int ret=0;
	
	if(fn-st<=128) {
		while(st<=fn) {
			if(B[st>>6]&(1ULL<<(st&63))) ret++;
			st++;
		}
	}
	else {
		while(st&63) {
			if(B[st>>6]&(1ULL<<(st&63))) ret++;
			st++;
		}
		while((fn&63)!=63) {
			if(B[fn>>6]&(1ULL<<(fn&63))) ret++;
			fn--;
		}
		if(fn-st<=2048) {
			while(st<=fn) {
				ret+=__builtin_popcountll(B[st>>6]);
				st+=64;
			}
		}
		else {
			while(st&1023) {
				ret+=__builtin_popcountll(B[st>>6]);
				st+=64;
			}
			while((fn&1023)!=1023) {
				ret+=__builtin_popcountll(B[fn>>6]);
				fn-=64;
			}
			if(st<fn) ret+=bt((fn+1)>>10)-bt((st>>10));
		}
	}
	
	return ret;
}

int main() {
	int N, M;
	RandGen rng;
	cin >> N >> M >> rng.x >> rng.y >> rng.z;

	init(N, M);

	long long hashSol = 0;

	for (long long i = 0; i < M; i++) {
		if (rng.random(2) == 0) {
			const int poz = rng.random(N);
			flipPosition(poz);
		}
		else {
			int st = rng.random(N), fn = rng.random(N);
			if (st > fn) {
				swap(st, fn);
			}
			hashSol ^= i * getCount(st, fn);
		}
	}

	cout << hashSol << "\n";
}

まとめ

何がしたかったんだろう。