[Codeforces Round #307(Div.2)] 551E-GukiZ and GukiZiana

发布于 2020-04-02  23 次阅读



这题时限给了 10s 也是好玩......
总的来说做法就是分块,修改的时候边上的块暴力修改后从小到大排序,中间的块就就一个 lazy 标记就行。查询的时候暴力枚举每一个块,块中二分查询位置即可。
一开始修改完了没有清空 lazy 标记还能过 14 个点也是绝了......

#include <bits/stdc++.h>
#define ll long long
#define ls id << 1
#define rs id << 1 | 1
#define mem(array, value, size, type) memset(array, value, ((size) + 5) * sizeof(type))
#define pb(x) push_back(x)
#define st(x) (1LL << (x))
#define pii pair<int, int>
using namespace std;
const int N = 500050;
const int inf = 0x3f3f3f3f;
const ll mod = 998244353LL;
clock_t TIME_START, TIME_END;
void program_end()
{
#ifdef ONLINE
    printf("\nTime used:
    system("pause");
#endif
}
int n, Q;
int belong[N], sz = 1225, tot;
struct Block
{
    int l, r;
    ll lazy;
} b[1050];
struct num
{
    int id;
    ll val;
    bool operator<(const num &x)
    {
        return val < x.val || (val == x.val && id < x.id);
    }
} a[N];
inline void add(int l, int r, int val)
{
    int L = belong[l], R = belong[r];
    for (int i = b[L].l; i <= b[L].r; ++i)
    {
        a[i].val += b[L].lazy;
        if (a[i].id >= l && a[i].id <= r)
            a[i].val += val;
    }
    if (L < R)
    {
        for (int i = b[R].l; i <= b[R].r; ++i)
        {
            a[i].val += b[R].lazy;
            if (a[i].id >= l && a[i].id <= r)
                a[i].val += val;
        }
    }
    for (int i = L + 1; i <= R - 1; ++i)
        b[i].lazy += val;
    sort(a + b[L].l, a + b[L].r + 1);
    if (L < R)
        sort(a + b[R].l, a + b[R].r + 1);
    b[L].lazy = b[R].lazy = 0;
}
inline int checkL(int i, int y)
{
    int L = b[i].l, R = b[i].r, ret = -1;
    while (L <= R)
    {
        int mid = (L + R) >> 1;
        if (a[mid].val <= y - b[i].lazy)
        {
            if (a[mid].val == y - b[i].lazy)
                ret = a[mid].id, R = mid - 1;
            else L = mid + 1;
        }
        else
            R = mid - 1;
    }
    return ret;
}
inline int checkR(int i, int y)
{
    int L = b[i].l, R = b[i].r, ret = -1;
    while (L <= R)
    {
        int mid = (L + R) >> 1;
        if (a[mid].val <= y - b[i].lazy)
        {
            if (a[mid].val == y - b[i].lazy)
                ret = a[mid].id;
            L = mid + 1;
        }
        else
            R = mid - 1;
    }
    return ret;
}
inline int query(int y)
{
    int retl = inf, retr = 0;
    for (int i = 1; i <= tot; ++i)
    {
        int posL = checkL(i, y);
        if (posL != -1)
            retl = min(retl, posL);
        int posR = checkR(i, y);
        if (posR != -1)
            retr = max(retr, posR);
    }
    if (retl == inf)
        return -1;
    else
        return retr - retl;
}
void pregao()
{
    // sz = sqrt(n);
    for (int i = 1; i <= 1000; ++i)
        b[i].l = inf;
    for (int i = 1; i <= n; ++i)
    {
        belong[i] = i / sz + 1;
        b[i / sz + 1].l = min(b[i / sz + 1].l, i);
        b[i / sz + 1].r = max(b[i / sz + 1].r, i);
    }
    tot = n / sz + 1;
    for (int i = 1; i <= tot; ++i)
    {
        sort(a + b[i].l, a + b[i].r + 1);
    }
}
void solve()
{
    scanf(
    for (int i = 1; i <= n; ++i)
        scanf(
    pregao();
    while (Q--)
    {
        int type, l, r, y;
        scanf(
        if (type == 1)
        {
            scanf(
            add(l, r, y);
        }
        else
        {
            scanf(
            int ans = query(y);
            printf(
        }
    }
}
int main()
{
    TIME_START = clock();
    int Test = 1;
    // cin >> Test;
    while (Test--)
        solve();
    TIME_END = clock();
    program_end();
    return 0;
}