結果

問題 No.469 区間加算と一致検索の問題
コンテスト
ユーザー anta
提出日時 2016-12-19 12:18:47
言語 C++14
(gcc 13.3.0 + boost 1.87.0)
結果
AC  
実行時間 1,104 ms / 5,000 ms
コード長 7,695 bytes
コンパイル時間 1,973 ms
コンパイル使用メモリ 192,944 KB
実行使用メモリ 128,528 KB
最終ジャッジ日時 2024-12-21 16:49:30
合計ジャッジ時間 24,344 ms
ジャッジサーバーID
（参考情報） 		judge3 / judge2
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 3
other AC * 49
権限があれば一括ダウンロードができます

ソースコード

diff # 

#include "bits/stdc++.h"
using namespace std;
#define rep(i,n) for(int (i)=0;(i)<(int)(n);++(i))
#define rer(i,l,u) for(int (i)=(int)(l);(i)<=(int)(u);++(i))
#define reu(i,l,u) for(int (i)=(int)(l);(i)<(int)(u);++(i))
static const int INF = 0x3f3f3f3f; static const long long INFL = 0x3f3f3f3f3f3f3f3fLL;
typedef vector<int> vi; typedef pair<int, int> pii; typedef vector<pair<int, int> > vpii; typedef long long ll;
template<typename T, typename U> static void amin(T &x, U y) { if (y < x) x = y; }
template<typename T, typename U> static void amax(T &x, U y) { if (x < y) x = y; }

struct PolynomialHash {
	static const int NumMods = 5;
	static const unsigned Mods[NumMods];
	typedef unsigned long long ull;
	struct Hash {
		unsigned hs[NumMods];
		Hash() { for (int k = 0; k < NumMods; ++k) hs[k] = 0; }
		explicit Hash(signed x) {
			for (int k = 0; k < NumMods; ++k) {
				signed y = x % (signed)Mods[k];
				if (y < 0) y += Mods[k];
				hs[k] = y;
			}
		}
		bool operator==(const Hash &that) const {
			bool res = true;
			for (int k = 0; k < NumMods; ++k)
				res &= hs[k] == that.hs[k];
			return res;
		}
		bool operator<(const Hash &that) const {
			for (int k = 0; k < NumMods; ++k)
				if (hs[k] != that.hs[k])
					return hs[k] < that.hs[k];
			return false;
		}
		Hash &operator+=(const Hash &that) {
			for (int k = 0; k < NumMods; ++k)
				if ((hs[k] += that.hs[k]) >= Mods[k])
					hs[k] -= Mods[k];
			return *this;
		}
		Hash operator+(const Hash &that) const { return Hash(*this) += that; }
		Hash &operator-=(const Hash &that) {
			for (int k = 0; k < NumMods; ++k)
				if ((hs[k] += Mods[k] - that.hs[k]) >= Mods[k])
					hs[k] -= Mods[k];
			return *this;
		}
		Hash operator-(const Hash &that) const { return Hash(*this) -= that; }
		Hash operator*(const Hash &that) const {
			Hash res;
			for (int k = 0; k < NumMods; ++k)
				res.hs[k] = (ull)hs[k] * that.hs[k] % Mods[k];
			return res;
		}
	};

	Hash seed;
	std::vector<Hash> powh;
	std::vector<Hash> sumpowh;

	PolynomialHash() {
		random_device rd;
		for (int k = 0; k < NumMods; ++k) {
			unsigned x;
			do x = rd(); while (x < 65536 || x >= Mods[k]);
			seed.hs[k] = x;
		}
	}

	void precomputePowerTable(int newSize) {
		int oldSize = (int)powh.size();
		if (oldSize >= newSize) return;
		powh.resize(newSize);
		sumpowh.resize(newSize);
		if (oldSize == 0) {
			powh[0] = Hash(1);
			sumpowh[0] = Hash();
		}
		for (int i = std::max(1, oldSize); i < newSize; i++) {
			powh[i] = powh[i - 1] * seed;
			sumpowh[i] = sumpowh[i - 1] + powh[i - 1];
		}
	}
	Hash append(const Hash &h, const Hash &g, int glen) const {
		Hash res;
		for (int k = 0; k < NumMods; ++k) {
			unsigned x = (unsigned)((ull)h.hs[k] * powh[glen].hs[k] % Mods[k]) + g.hs[k];
			res.hs[k] = x >= Mods[k] ? x - Mods[k] : x;
		}
		return res;
	}
};
const unsigned PolynomialHash::Mods[PolynomialHash::NumMods] = { 2147483647U, 2147483629U, 2147483587U, 2147483579U, 2147483563U };
namespace std {
	template<> struct hash<PolynomialHash::Hash> {
		size_t operator()(const PolynomialHash::Hash &h) const {
			return h.hs[0];
		}
	};
}

PolynomialHash ph;
using Val = int;
struct Sum {
	PolynomialHash::Hash h;
	int size;
	Sum() : h(), size(0) {}
	Sum(const Val &val, int pos) : h(val), size(1) { }
	Sum &operator+=(const Sum &that) {
		h = ph.append(h, that.h, that.size);
		size += that.size;
		return *this;
	}
	Sum operator+(const Sum &that) const { return Sum(*this) += that; }
};
struct Add {
	int add;
	Add() : add(0) { }
	Add &operator+=(const Add &that) { add += that.add; return *this; }
	void addToVal(Val &val, int pos) const { val += add; }
	void addToSum(Sum &sum, int left, int right) const {
		if (add != 0)
			sum.h += ph.sumpowh[right - left] * PolynomialHash::Hash(add);
	}
};

struct SegmentTree {
	vector<Val> leafs;
	vector<Sum> nodes;
	vector<Add> add;
	vector<int> leftpos, rightpos;
	int n, n2;
	void init(int n_, const Val &v = Val()) { init(vector<Val>(n_, v)); }
	void init(const vector<Val> &u) {
		n = 1; while (n < (int)u.size()) n *= 2;
		n2 = (n - 1) / 2 + 1;
		leafs = u; leafs.resize(n, Val());
		nodes.resize(n);
		for (int i = n - 1; i >= n2; --i)
			nodes[i] = Sum(leafs[i * 2 - n], i * 2 - n) + Sum(leafs[i * 2 + 1 - n], i * 2 + 1 - n);
		for (int i = n2 - 1; i > 0; --i)
			nodes[i] = nodes[i * 2] + nodes[i * 2 + 1];
		add.assign(n, Add());

		leftpos.resize(n); rightpos.resize(n);
		for (int i = n - 1; i >= n2; --i) {
			leftpos[i] = i * 2 - n;
			rightpos[i] = (i * 2 + 1 - n) + 1;
		}
		for (int i = n2 - 1; i > 0; --i) {
			leftpos[i] = leftpos[i * 2];
			rightpos[i] = rightpos[i * 2 + 1];
		}
	}
	Val get(int i) {
		int indices[128];
		int k = getIndices(indices, i, i + 1);
		propagateRange(indices, k);
		return leafs[i];
	}
	Sum getRangeCommutative(int i, int j) {
		int indices[128];
		int k = getIndices(indices, i, j);
		propagateRange(indices, k);
		Sum res = Sum();
		for (int l = i + n, r = j + n; l < r; l >>= 1, r >>= 1) {
			if (l & 1) res += sum(l++);
			if (r & 1) res += sum(--r);
		}
		return res;
	}
	Sum getRange(int i, int j) {
		int indices[128];
		int k = getIndices(indices, i, j);
		propagateRange(indices, k);
		Sum res = Sum();
		for (; i && i + (i&-i) <= j; i += i&-i)
			res += sum((n + i) / (i&-i));
		for (k = 0; i < j; j -= j&-j)
			indices[k++] = (n + j) / (j&-j) - 1;
		while (--k >= 0) res += sum(indices[k]);
		return res;
	}
	void set(int i, const Val &x) {
		int indices[128];
		int k = getIndices(indices, i, i + 1);
		propagateRange(indices, k);
		leafs[i] = x;
		mergeRange(indices, k);
	}
	void addToRange(int i, int j, const Add &x) {
		if (i >= j) return;
		int indices[128];
		int k = getIndices(indices, i, j);
		propagateRange(indices, k);
		int l = i + n, r = j + n;
		if (l & 1) { int p = (l++) - n; x.addToVal(leafs[p], p); }
		if (r & 1) { int p = (--r) - n; x.addToVal(leafs[p], p); }
		for (l >>= 1, r >>= 1; l < r; l >>= 1, r >>= 1) {
			if (l & 1) add[l++] += x;
			if (r & 1) add[--r] += x;
		}
		mergeRange(indices, k);
	}
private:
	int getIndices(int indices[], int i, int j) const {
		int k = 0, l, r;
		if (i >= j) return 0;
		for (l = (n + i) >> 1, r = (n + j - 1) >> 1; l != r; l >>= 1, r >>= 1) {
			indices[k++] = l;
			indices[k++] = r;
		}
		for (; l; l >>= 1) indices[k++] = l;
		return k;
	}
	void propagateRange(int indices[], int k) {
		for (int i = k - 1; i >= 0; --i)
			propagate(indices[i]);
	}
	void mergeRange(int indices[], int k) {
		for (int i = 0; i < k; ++i)
			merge(indices[i]);
	}
	inline void propagate(int i) {
		if (i >= n) return;
		add[i].addToSum(nodes[i], leftpos[i], rightpos[i]);
		if (i * 2 < n) {
			add[i * 2] += add[i];
			add[i * 2 + 1] += add[i];
		}
		else {
			add[i].addToVal(leafs[i * 2 - n], i * 2 - n);
			add[i].addToVal(leafs[i * 2 + 1 - n], i * 2 + 1 - n);
		}
		add[i] = Add();
	}
	inline void merge(int i) {
		if (i >= n) return;
		nodes[i] = sum(i * 2) + sum(i * 2 + 1);
	}
	inline Sum sum(int i) {
		propagate(i);
		return i < n ? nodes[i] : Sum(leafs[i - n], i - n);
	}
};

int main() {
	int N; int Q;
	while (~scanf("%d%d", &N, &Q)) {
		ph.precomputePowerTable((N + 1) * 2);
		SegmentTree segt;
		segt.init(vector<Val>(N));
		unordered_map<PolynomialHash::Hash, int> firstOccurence;
		firstOccurence.emplace(make_pair(segt.getRange(0, N).h, 0));
		int lastAns = 0;
		for (int ii = 0; ii < Q; ++ii) {
			char ty[10];
			scanf("%s", ty);
			if (*ty == '!') {
				int L; int R; int K;
				scanf("%d%d%d", &L, &R, &K);
				Add add; add.add = K;
				segt.addToRange(L, R, add);
				auto h = segt.getRange(0, N).h;
				lastAns = firstOccurence.emplace(make_pair(h, ii + 1)).first->second;
			}
			else if (*ty == '?') {
				printf("%d\n", lastAns);
			}
			else abort();
		}
	}
	return 0;
}
0