【CF482B】Interesting Array
We'll call an array of n non-negative integers a[1], a[2], ..., a[n] interesting, if it meets m constraints. The i-th of the m constraints consists of three integers li, ri, qi (1 ≤ li ≤ ri ≤ n) meaning that value 
should be equal to qi.
should be equal to qi.
Your task is to find any interesting array of n elements or state that such array doesn't exist.
Expression x&y means the bitwise AND of numbers x and y. In programming languages C++, Java and Python this operation is represented as "&", in Pascal — as "and".
Input
The first line contains two integers n, m (1 ≤ n ≤ 105, 1 ≤ m ≤ 105) — the number of elements in the array and the number of limits.
Each of the next m lines contains three integers li, ri, qi (1 ≤ li ≤ ri ≤ n, 0 ≤ qi < 230) describing the i-th limit.
Output
If the interesting array exists, in the first line print "YES" (without the quotes) and in the second line print n integers a[1], a[2], ..., a[n] (0 ≤ a[i] < 230) decribing the interesting array. If there are multiple answers, print any of them.
If the interesting array doesn't exist, print "NO" (without the quotes) in the single line.
Examples
Input
3 1
1 3 3
1 3 3
Output
YES
3 3 3
3 3 3
Input
3 2
1 3 3
1 3 2
1 3 3
1 3 2
Output
NO
#include <cstdio>
#include <algorithm>
const int N = 1000 * 1000;
const int MAXBIT = 30;
int l[N], r[N], q[N], a[N], t[4 * N];
int sum[N];
inline void build(int v, int l, int r)
{
if (l + 1 == r)
{
t[v] = a[l];
return;
}
int mid = (l + r) >> 1;
build(v * 2, l, mid);
build(v * 2 + 1, mid, r);
t[v] = t[v * 2] & t[v * 2 + 1];
}
inline int query(int v, int l, int r, int L, int R)
{
if (l == L && r == R)
{
return t[v];
}
int mid = (L + R) >> 1;
int ans = (1ll << MAXBIT) - 1;
if (l < mid)
ans &= query(v * 2, l, std::min(r, mid), L, mid);
if (mid < r)
ans &= query(v * 2 + 1, std::max(l, mid), r, mid, R);
return ans;
}
int main()
{
int n, m;
scanf("%d %d\n", &n, &m);
for (int i = 0; i < m; i++)
{
scanf("%d %d %d\n", &l[i], &r[i], &q[i]);
l[i]--;
}
for (int bit = 0; bit <= MAXBIT; bit++)
{
for (int i = 0; i < n; i++)
sum[i] = 0;
for (int i = 0; i < m; i++)
{
if ((q[i] >> bit) & 1)
{
sum[l[i]]++;
sum[r[i]]--;
}
}
for (int i = 0; i < n; i++)
{
if (i > 0)
sum[i] += sum[i - 1];
if (sum[i] > 0)
{
a[i] |= (1 << bit);
}
}
}
build(1, 0, n);
for (int i = 0; i < m; i++)
{
if (query(1, l[i], r[i], 0, n) != q[i])
{
puts("NO");
return 0;
}
}
puts("YES");
for (int i = 0; i < n; i++)
{
if (i)
printf(" ");
printf("%d", a[i]);
}
puts("");
}
大概就是先做了一个差分，再搞线段树
#pragma GCC optimize("Ofast,no-stack-protector,unroll-loops,fast-math")
#pragma GCC target("sse,sse2,sse3,ssse3,sse4.1,sse4.2,avx,avx2,popcnt,tune=native")
#include "bits/stdc++.h"
#define mem(x) memset((x), 0, sizeof((x)))
#define il __attribute__((always_inline))
using namespace std;
typedef long long ll;
typedef long double ld;
typedef unsigned long long ull;
#if __cplusplus > 201403L
#define r
#else
#define r register
#endif
#define c const
namespace _c
{
c double pi = acos(-1.0);
namespace min
{
c int i8 = -128;
c int i16 = -32768;
c int i = -2147483647 - 1;
c ll l = -9223372036854775807LL - 1;
} // namespace min
namespace max
{
c int i8 = 127;
c int i16 = 32767;
c int i = 2147483647;
c ll l = 9223372036854775807LL;
} // namespace max
} // namespace _c
namespace _f
{
template <typename T>
inline c T gcd(T m, T n)
{
while (n != 0)
{
T t = m % n;
m = n;
n = t;
}
return m;
}
template <typename T>
inline c T abs(c T &a)
{
return a > 0 ? a : -a;
}
template <typename T>
inline T pow(T a, T b)
{
T res = 1;
while (b > 0)
{
if (b & 1)
{
res = res * a;
}
a = a * a;
b >>= 1;
}
return res;
}
template <typename T>
inline T pow(T a, T b, c T &m)
{
a %= m;
T res = 1;
while (b > 0)
{
if (b & 1)
{
res = res * a % m;
}
a = a * a % m;
b >>= 1;
}
return res % m;
}
} // namespace _f
namespace io
{
template <typename T>
inline T read()
{
r T res = 0, neg = 1;
char g = getchar();
for (; !isdigit(g); g = getchar())
{
if (g == '-')
{
neg = -1;
}
}
for (; isdigit(g); g = getchar())
{
res = res * 10 + g - '0';
}
return res * neg;
}
template <typename T>
inline void read(T &t)
{
t = read<T>();
}
template <typename T>
inline void readln(c T first, c T last)
{
for (r T it = first; it != last; it++)
{
read(*it);
}
}
template <typename T>
inline void _write(T x)
{
if (x < 0)
{
putchar('-');
x = -x;
}
if (x > 9)
{
_write(x / 10);
}
putchar(x % 10 + '0');
}
template <typename T>
inline void write(c T &x, c char &sep = ' ')
{
_write(x);
putchar(sep);
}
template <typename T>
inline void writeln(c T &x)
{
write(x, '\n');
}
template <typename T>
inline void writeln(c T first, c T last, c char &sep = ' ', c char &ends = '\n')
{
for (r T it = first; it != last; it++)
{
write(*it, sep);
}
putchar(ends);
}
#if __cplusplus >= 201103L
template <typename T, typename... Args>
void read(T &x, Args &... args)
{
read(x);
read(args...);
}
#endif
} // namespace io
#undef c
#undef r
constexpr int _N = 1000;
constexpr int N = _N * _N;
constexpr int MAX_BIT = 30;
int l[N], r[N], q[N];
int a[N];
int sum[N];
struct SegTree
{
#define ls ((rt) << 1)
#define rs ((rt) << 1 | 1)
int t[4 * N];
inline void build(int rt, int l, int r)
{
if (l + 1 == r)
{
t[rt] = a[l];
}
else
{
int mid = (l + r) >> 1;
build(ls, l, mid);
build(rs, mid, r);
t[rt] = t[ls] & t[rs];
}
}
inline int query(int rt, int l, int r, int ql, int qr)
{
if (l == ql && r == qr)
{
return t[rt];
}
else
{
int mid = (ql + qr) >> 1;
int ans = (1ll << MAX_BIT) - 1;
if (l < mid)
{
ans &= query(ls, l, std::min(r, mid), ql, mid);
}
if (mid < r)
{
ans &= query(rs, std::max(l, mid), r, mid, qr);
}
return ans;
}
}
#undef ls
#undef rs
} Seg;
int n, m;
int main()
{
#define rd(x) io::read(x)
rd(n), rd(m);
for (register int i = 0; i < m; i++)
{
rd(l[i]), rd(r[i]), rd(q[i]);
l[i]--;
}
#undef rd
for (register int bit = 0; bit <= MAX_BIT; bit++)
{
for (register int i = 0; i < n; i++)
{
sum[i] = 0;
}
for (register int i = 0; i < m; i++)
{
if ((q[i] >> bit) & 1)
{
sum[l[i]]++;
sum[r[i]]--;
}
}
for (register int i = 0; i < n; i++)
{
if (i > 0)
{
sum[i] += sum[i - 1];
}
if (sum[i] > 0)
{
a[i] |= (1 << bit);
}
}
}
Seg.build(1, 0, n);
for (register int i = 0; i < m; i++)
{
if (Seg.query(1, l[i], r[i], 0, n) != q[i])
{
puts("NO");
return 0;
}
}
puts("YES");
io::writeln(a, a + n);
}
评论
发表评论