QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#308037#6427. Just Another Game of StonesYaremaWA 0ms3544kbC++143.6kb2024-01-19 14:01:272024-01-19 14:01:28

Judging History

你现在查看的是最新测评结果

  • [2024-01-19 14:01:28]
  • 评测
  • 测评结果:WA
  • 用时:0ms
  • 内存:3544kb
  • [2024-01-19 14:01:27]
  • 提交

answer

#include <bits/stdc++.h>

using namespace std;

#define FOR(i, a, b) for(int i = (a); i < (b); i++)
#define RFOR(i, a, b) for(int i = (a) - 1; i >= (b); i--)
#define SZ(a) int(a.size())
#define ALL(a) a.begin(), a.end()
#define PB push_back
#define MP make_pair
#define F first
#define S second

typedef long long LL;
typedef vector<int> VI;
typedef pair<int, int> PII;
typedef double db;

const int LOG = 31;
const LL INF = 1ll << 47;

struct Node
{
	LL mn, cnt, mn2, x, ps;
	int c[LOG];
	
	Node()
	{
		mn = INF;
		cnt = 0;
		mn2 = INF;
		x = 0;
		ps = -1;
		fill(c, c + LOG, 0);
	}
	
	void out()
	{
		cerr << mn << ' ' << cnt << ' ' << mn2 << ' ' << x << '\n';
		FOR (j, 0, 4)
			cerr << c[j] << ' ';
		cerr << '\n';		
	}
};

struct Segtree
{
	
	int n;
	vector<Node> t;
	
	void init(int _n)
	{
		n = 1;
		while (n < _n) n *= 2;
		t.resize(2 * n + 1);
	}
	
	Node combine(Node a, Node b)
	{
		Node res;
		if (a.mn == b.mn)
		{
			res.mn = a.mn;
			res.cnt = a.cnt + b.cnt;
			res.mn2 = min(a.mn2, b.mn2);
		}
		else
		{
			res.mn = min(a.mn, b.mn);
			res.cnt = a.mn < b.mn ? a.cnt : b.cnt;
			res.mn2 = min({a.mn2, b.mn2, max(a.mn, b.mn)});
		}
		res.x = a.x ^ b.x;
		FOR (i, 0, LOG)
			res.c[i] = a.c[i] + b.c[i];
		return res;
	}
	
	void build(int v, int tl, int tr, const vector<LL>& a)
	{
		if (tl + 1 == tr)
		{
			if (tl < SZ(a))
			{
				t[v].mn = a[tl];
				t[v].cnt = 1;
				t[v].mn2 = INF;
				t[v].x = a[tl];
				t[v].ps = -1;
				FOR (i, 0, LOG) t[v].c[i] = (a[tl] >> i) & 1;
			}
			return;
		}
		int tm = (tl + tr) / 2;
		build(v * 2 + 1, tl, tm, a);
		build(v * 2 + 2, tm, tr, a);
		t[v] = combine(t[v * 2 + 1], t[v * 2 + 2]);
	}
	
	void build(const vector<LL>& a)
	{
		init(SZ(a));
		build(0, 0, n, a);
	}
	
	Node query(int v, int tl, int tr, int l, int r)
	{
		if (l >= tr || tl >= r)
			return {};
		if (l <= tl && tr <= r)
			return t[v];
		push(v);
		int tm = (tl + tr) / 2;
		return combine(query(v * 2 + 1, tl, tm, l, r),
					   query(v * 2 + 2, tm, tr, l, r));
	}
	
	Node query(int l, int r)
	{
		return query(0, 0, n, l, r);
	}
	
	void push(int v)
	{
		if (v * 2 + 1 >= SZ(t) || t[v].ps == -1)
		{
			t[v].ps = -1;
			return;
		}
		up(t[v * 2 + 1], t[v].ps);
		up(t[v * 2 + 2], t[v].ps);
		t[v].ps = -1;
	}
	
	void up(Node& nd, LL x)
	{		
		if (nd.mn >= x)
			return;
		if (nd.cnt & 1)
			nd.x ^= nd.mn ^ x;
		FOR (i, 0, LOG)
		{
			nd.c[i] -= ((nd.mn >> i) & 1) * nd.cnt;
			nd.c[i] += ((x >> i) & 1) * nd.cnt;
		}
		nd.mn = x;
		nd.ps = max(nd.ps, x);
	}
	
	void upd(int v, int tl, int tr, int l, int r, LL x)
	{
		if (l >= tr || tl >= r || t[v].mn >= x)
			return;
		if (l <= tl && tr <= r && t[v].mn2 > x)
		{
			up(t[v], x);
			return;
		}
		push(v);
		int tm = (tl + tr) / 2;
		upd(v * 2 + 1, tl, tm, l, r, x);
		upd(v * 2 + 2, tm, tr, l, r, x);
		t[v] = combine(t[v * 2 + 1], t[v * 2 + 2]);
	}
	
	void upd(int l, int r, LL x)
	{
		upd(0, 0, n, l, r, x);
	}
};

int main()
{
	ios::sync_with_stdio(0); 
	cin.tie(0);
	cout << fixed << setprecision(15);
	
	int n, m;
	cin >> n >> m;
	vector<LL> a(n);
	FOR (i, 0, n) cin >> a[i];
	Segtree st;
	st.build(a);
	FOR (i, 0, m)
	{
		int t, l, r;
		LL x;
		cin >> t >> l >> r >> x;
		l--;
		if (t == 1)
		{
			st.upd(l, r, x);
		}
		else
		{
			auto nd = st.query(l, r);
			int xr = x ^ nd.x;
			if (x == 0)
				cout << 0 << '\n';
			else
			{
				int bt = 31 - __builtin_clz(xr);
				cout << nd.c[bt] + ((x >> bt) & 1) << '\n';
			}
		}
	}
	
	return 0;
}

詳細信息

Test #1:

score: 0
Wrong Answer
time: 0ms
memory: 3544kb

input:

5 4
1 2 1 4 1
2 1 3 1
1 2 4 3
2 2 4 4
2 1 4 4

output:

1
2
3

result:

wrong answer 2nd numbers differ - expected: '0', found: '2'