[CF 817F] MEX Queries(라인 트리)
10612 단어 Codeforces세그먼트 트리
Description
길이 1018 1018의 0101 서열을 유지하고 도자기 구간에 값을 부여하고 구간에서 반전을 취하며 첫 번째 0의 위치를 조회해야 한다.
Solution
이산화 후 라인 트리로 역표기, 부치표기를 유지하면 됩니다.
Code
/************************************************
* Au: Hany01
* Date: Aug 2nd, 2018
* Prob: CF817 F
* Email: [email protected]
* Inst: Yali High School
************************************************/
#include
using namespace std;
typedef long long LL;
typedef pair<int, int> PII;
#define rep(i, j) for (register int i = 0, i##_end_ = (j); i < i##_end_; ++ i)
#define For(i, j, k) for (register int i = (j), i##_end_ = (k); i <= i##_end_; ++ i)
#define Fordown(i, j, k) for (register int i = (j), i##_end_ = (k); i >= i##_end_; -- i)
#define Set(a, b) memset(a, b, sizeof(a))
#define Cpy(a, b) memcpy(a, b, sizeof(a))
#define x first
#define y second
#define pb(a) push_back(a)
#define mp(a, b) make_pair(a, b)
#define SZ(a) ((int)(a).size())
#define INF (0x3f3f3f3f)
#define INF1 (2139062143)
#define debug(...) fprintf(stderr, __VA_ARGS__)
#define y1 wozenmezhemecaia
template <typename T> inline bool chkmax(T &a, T b) { return a < b ? a = b, 1 : 0; }
template <typename T> inline bool chkmin(T &a, T b) { return b < a ? a = b, 1 : 0; }
template <typename T> inline T read() {
static T _, __; static char c_;
for (_ = 0, __ = 1, c_ = getchar(); c_ < '0' || c_ > '9'; c_ = getchar()) if (c_ == '-') __ = -1;
for ( ; c_ >= '0' && c_ <= '9'; c_ = getchar()) _ = (_ << 1) + (_ << 3) + (c_ ^ 48);
return _ * __;
}
const int maxn = 1e5 + 5;
struct Op { int ty; LL l, r; }op[maxn];
LL ls[maxn << 2];
int co[maxn * 50], n, tag[maxn * 50], N, sv[maxn * 50];
#define mid ((l + r) >> 1)
#define lc (t << 1)
#define rc (lc | 1)
inline void maintain(int t) {
if (co[lc] == co[rc]) co[t] = co[lc]; else co[t] = -1;
}
inline void rev(int t) {
if (sv[t] >= 0) {
sv[t] ^= 1, co[t] ^= 1;
} else {
tag[t] ^= 1;
if (co[t] >= 0) co[t] ^= 1;
}
}
inline void pushdown(int t) {
if (sv[t] >= 0) {
sv[lc] = sv[rc] = co[lc] = co[rc] = sv[t];
tag[lc] = tag[rc] = 0;//!!!!!
sv[t] = -1;
}
if (tag[t]) {
tag[t] = 0;
rev(lc), rev(rc);
}
}
void build(int t, int l, int r) {
sv[t] = -1;
if (l != r) build(lc, l, mid), build(rc, mid + 1, r);
}
void update1(int t, int l, int r, int x, int y, int c) {
if (x <= l && r <= y) { co[t] = sv[t] = c, tag[t] = 0; return; }
pushdown(t);
if (x <= mid) update1(lc, l, mid, x, y, c);
if (y > mid) update1(rc, mid + 1, r, x, y, c);
maintain(t);
}
void update2(int t, int l, int r, int x, int y) {
if (x <= l && r <= y) { rev(t); return; }
pushdown(t);
if (x <= mid) update2(lc, l, mid, x, y);
if (y > mid) update2(rc, mid + 1, r, x, y);
maintain(t);
}
int query(int t, int l, int r) {
if (co[t] == 0 || !t) return l;
pushdown(t);
if (co[lc] == 1) return query(rc, mid + 1, r);
return query(lc, l, mid);
}
int main()
{
#ifdef hany01
freopen("cf817f.in", "r", stdin);
freopen("cf817f.out", "w", stdout);
#endif
n = read<int>(), ls[N = 1] = 1;
For(i, 1, n) {
op[i] = Op{read<int>(), read(), read()};
ls[++ N] = op[i].l, ls[++ N] = op[i].r;
ls[++ N] = op[i].r + 1;
ls[++ N] = op[i].l + 1;
}
sort(ls + 1, ls + 1 + N), N = unique(ls + 1, ls + 1 + N) - ls - 1;
build(1, 1, N);
For(i, 1, n) {
if (op[i].ty < 3)
update1(1, 1, N, lower_bound(ls + 1, ls + 1 + N, op[i].l) - ls, lower_bound(ls + 1, ls + 1 + N, op[i].r) - ls, op[i].ty & 1);
else
update2(1, 1, N, lower_bound(ls + 1, ls + 1 + N, op[i].l) - ls, lower_bound(ls + 1, ls + 1 + N, op[i].r) - ls);
printf("%lld
", ls[query(1, 1, N)]);
}
return 0;
}
이 내용에 흥미가 있습니까?
현재 기사가 여러분의 문제를 해결하지 못하는 경우 AI 엔진은 머신러닝 분석(스마트 모델이 방금 만들어져 부정확한 경우가 있을 수 있음)을 통해 가장 유사한 기사를 추천합니다:
Codeforces 1287C Garland제목 링크:Codeforces 1287C Garland 사고방식: 우리기dp[i][j][0]와 dp[i][j][1]는 각각 i개가 홀수/짝수이고 앞의 i개 안에 j개의 짝수가 있는 상황에서 i개의 최소 복잡도.첫 번...
텍스트를 자유롭게 공유하거나 복사할 수 있습니다.하지만 이 문서의 URL은 참조 URL로 남겨 두십시오.
CC BY-SA 2.5, CC BY-SA 3.0 및 CC BY-SA 4.0에 따라 라이센스가 부여됩니다.