Loading [MathJax]/extensions/tex2jax.js

T44990:不认识题解

思路

我们可以考虑使用线段树来维护区间的面积(对于一对不认识的人,可以在二维空间中用一个边为\(1\)的块来表示。这时我们的问题便转换成为在坐标系中某一范围内的面积(面积就是区间内认识的人数)。我们再进行研究,就会发现每一次操作一次区间,我们操作的图形在二维坐标系上就会表示成两个对点落在\(y=x\)这条直线上。我们首先给直线\(y=x\)上的点描黑(自己总会认识自己),然后写一个线段树。我们在合并两个区间的时候需要注意,如果合并时涉及到两个矩形重叠,那么我们需要取最高的值来表示矩形的上边缘。在区间内,上边缘的高度一定是单调递增的,所以我们可以二分出一个高度小于覆盖高度的偏移量,这样可以加速合并。具体请看代码:

代码

Plain text
Copy to clipboard
Open code in new window
EnlighterJS 3 Syntax Highlighter
// T44990.cpp
#include <iostream>
#include <cstdio>
#include <algorithm>
#define ls (p << 1)
#define rs ((p << 1) | 1)
#define mid ((l + r) >> 1)
#define ll long long
using namespace std;
const ll maxn = 1000000 + 2000;
ll n, q, xl, xr, sum[maxn << 2], upper[maxn << 2], tag[maxn << 2];
// segment tree;
void pushdown(ll p, ll l, ll r)
{
if (tag[p] != 0)
{
tag[ls] = tag[rs] = tag[p];
upper[ls] = max(upper[ls], tag[p]);
upper[rs] = max(upper[rs], tag[p]);
sum[ls] = 1LL * tag[p] * (mid - l + 1);
sum[rs] = 1LL * tag[p] * (r - mid);
tag[p] = 0;
}
}
void pushup(ll p)
{
sum[p] = sum[ls] + sum[rs];
upper[p] = max(upper[ls], upper[rs]);
}
void build(ll l, ll r, ll p)
{
if (l == r)
{
sum[p] = upper[p] = l;
return;
}
build(l, mid, ls);
build(mid + 1, r, rs);
pushup(p);
}
void update(ll ql, ll qr, ll l, ll r, ll p, ll c)
{
if (ql > r || qr < l)
return;
if (ql <= l && r <= qr)
{
sum[p] = 1LL * (r - l + 1) * c, tag[p] = upper[p] = c;
return;
}
pushdown(p, l, r);
update(ql, qr, l, mid, ls, c);
update(ql, qr, mid + 1, r, rs, c);
pushup(p);
}
ll query(ll ql, ll qr, ll l, ll r, ll p)
{
if (ql > r || qr < l)
return 0;
if (ql <= l && r <= qr)
return sum[p];
pushdown(p, l, r);
return query(ql, qr, l, mid, ls) + query(ql, qr, mid + 1, r, rs);
}
ll find(ll l, ll r, ll p, ll strd)
{
if (l == r)
return l;
pushdown(p, l, r);
if (upper[ls] >= strd)
return find(l, mid, ls, strd);
else
return find(mid + 1, r, rs, strd);
}
int main()
{
scanf("%lld%lld", &n, &q);
build(0, n, 1);
ll lastans = 0;
for (ll i = 0; i < q; i++)
{
scanf("%lld%lld", &xl, &xr);
xl ^= lastans, xr ^= lastans;
ll pos = find(0, n, 1, xr) - 1;
if (pos < xl)
lastans = 0;
else
{
ll res = query(xl, pos, 0, n, 1);
lastans = 1LL * (pos - xl + 1) * xr - res;
update(xl, pos, 0, n, 1, xr);
}
printf("%lld\n", lastans);
}
return 0;
}
// T44990.cpp #include <iostream> #include <cstdio> #include <algorithm> #define ls (p << 1) #define rs ((p << 1) | 1) #define mid ((l + r) >> 1) #define ll long long using namespace std; const ll maxn = 1000000 + 2000; ll n, q, xl, xr, sum[maxn << 2], upper[maxn << 2], tag[maxn << 2]; // segment tree; void pushdown(ll p, ll l, ll r) { if (tag[p] != 0) { tag[ls] = tag[rs] = tag[p]; upper[ls] = max(upper[ls], tag[p]); upper[rs] = max(upper[rs], tag[p]); sum[ls] = 1LL * tag[p] * (mid - l + 1); sum[rs] = 1LL * tag[p] * (r - mid); tag[p] = 0; } } void pushup(ll p) { sum[p] = sum[ls] + sum[rs]; upper[p] = max(upper[ls], upper[rs]); } void build(ll l, ll r, ll p) { if (l == r) { sum[p] = upper[p] = l; return; } build(l, mid, ls); build(mid + 1, r, rs); pushup(p); } void update(ll ql, ll qr, ll l, ll r, ll p, ll c) { if (ql > r || qr < l) return; if (ql <= l && r <= qr) { sum[p] = 1LL * (r - l + 1) * c, tag[p] = upper[p] = c; return; } pushdown(p, l, r); update(ql, qr, l, mid, ls, c); update(ql, qr, mid + 1, r, rs, c); pushup(p); } ll query(ll ql, ll qr, ll l, ll r, ll p) { if (ql > r || qr < l) return 0; if (ql <= l && r <= qr) return sum[p]; pushdown(p, l, r); return query(ql, qr, l, mid, ls) + query(ql, qr, mid + 1, r, rs); } ll find(ll l, ll r, ll p, ll strd) { if (l == r) return l; pushdown(p, l, r); if (upper[ls] >= strd) return find(l, mid, ls, strd); else return find(mid + 1, r, rs, strd); } int main() { scanf("%lld%lld", &n, &q); build(0, n, 1); ll lastans = 0; for (ll i = 0; i < q; i++) { scanf("%lld%lld", &xl, &xr); xl ^= lastans, xr ^= lastans; ll pos = find(0, n, 1, xr) - 1; if (pos < xl) lastans = 0; else { ll res = query(xl, pos, 0, n, 1); lastans = 1LL * (pos - xl + 1) * xr - res; update(xl, pos, 0, n, 1, xr); } printf("%lld\n", lastans); } return 0; }
// T44990.cpp
#include <iostream>
#include <cstdio>
#include <algorithm>
#define ls (p << 1)
#define rs ((p << 1) | 1)
#define mid ((l + r) >> 1)
#define ll long long
using namespace std;
const ll maxn = 1000000 + 2000;
ll n, q, xl, xr, sum[maxn << 2], upper[maxn << 2], tag[maxn << 2];
// segment tree;
void pushdown(ll p, ll l, ll r)
{
    if (tag[p] != 0)
    {
        tag[ls] = tag[rs] = tag[p];
        upper[ls] = max(upper[ls], tag[p]);
        upper[rs] = max(upper[rs], tag[p]);
        sum[ls] = 1LL * tag[p] * (mid - l + 1);
        sum[rs] = 1LL * tag[p] * (r - mid);
        tag[p] = 0;
    }
}

void pushup(ll p)
{
    sum[p] = sum[ls] + sum[rs];
    upper[p] = max(upper[ls], upper[rs]);
}

void build(ll l, ll r, ll p)
{
    if (l == r)
    {
        sum[p] = upper[p] = l;
        return;
    }
    build(l, mid, ls);
    build(mid + 1, r, rs);
    pushup(p);
}

void update(ll ql, ll qr, ll l, ll r, ll p, ll c)
{
    if (ql > r || qr < l)
        return;
    if (ql <= l && r <= qr)
    {
        sum[p] = 1LL * (r - l + 1) * c, tag[p] = upper[p] = c;
        return;
    }
    pushdown(p, l, r);
    update(ql, qr, l, mid, ls, c);
    update(ql, qr, mid + 1, r, rs, c);
    pushup(p);
}

ll query(ll ql, ll qr, ll l, ll r, ll p)
{
    if (ql > r || qr < l)
        return 0;
    if (ql <= l && r <= qr)
        return sum[p];
    pushdown(p, l, r);
    return query(ql, qr, l, mid, ls) + query(ql, qr, mid + 1, r, rs);
}

ll find(ll l, ll r, ll p, ll strd)
{
    if (l == r)
        return l;
    pushdown(p, l, r);
    if (upper[ls] >= strd)
        return find(l, mid, ls, strd);
    else
        return find(mid + 1, r, rs, strd);
}

int main()
{
    scanf("%lld%lld", &n, &q);
    build(0, n, 1);
    ll lastans = 0;
    for (ll i = 0; i < q; i++)
    {
        scanf("%lld%lld", &xl, &xr);
        xl ^= lastans, xr ^= lastans;
        ll pos = find(0, n, 1, xr) - 1;
        if (pos < xl)
            lastans = 0;
        else
        {
            ll res = query(xl, pos, 0, n, 1);
            lastans = 1LL * (pos - xl + 1) * xr - res;
            update(xl, pos, 0, n, 1, xr);
        }
        printf("%lld\n", lastans);
    }
    return 0;
}

Leave a Reply

Your email address will not be published. Required fields are marked *