2023/11/23

1798C - Candy Store

只能说gcd，lcm的题目还是练少了，一些性质都不知道。

对于一段可以用同一个标签的区间，我们知道他们的c是一样的，c=di*bi，每一个物品的bi固定，那么c就一定是lcm{bi..bn}，因为c要能整除任何一个bi。然后我们来看可以自己决定的di，ai%di==0.而每一个物品的di=c/bi

所以ai%c/bi0 推出 ai*bi%c0. c就是gcd{ai * bi...an bn};*

所以一段区间合法,就是我们的c要取得合法.另外__gcd(0,a)=a

#include <bits/stdc++.h>
using namespace std;
#define Acode ios::sync_with_stdio(false), cin.tie(0), cout.tie(0)
#define int long long
#define endl '\n'
const int N = 2e5 + 10;
int a[N], s[N];
int b[N];

int lcm(int a, int b)
{
    return a * b / __gcd(a, b);
}

void solve()
{
    int n;
    cin >> n;
    int A = 0, B = 1, ans = 1;
    for (int i = 1; i <= n; i++)
    {
        int a, b;
        cin >> a >> b;
        A = __gcd(A, a * b);
        B = lcm(b, B);
        if (A % B)
        {
            ans++;
            A = a * b;
            B = b;
        }
    }
    cout << ans << endl;
}

signed main()
{
    Acode;
    int T = 1;
    cin >> T;
    while (T--)
    {
        solve();
    }
    return 0;
}

Educational Codeforces Round 149 (Rated for Div. 2) solve(3/6)

下午上课vp，打了一个小时，电脑没电了

有点卡C，最近在学数据结构，cf也跟上吧。感觉最近状态挺一般的，训练什么的打的不是很顺，呜呜呜

https://www.bilibili.com/video/BV1fz4y1c7E5/?vd_source=7b3be65640481106bef731ef741a960f

线段树

info的解释：我们是对每个节点都看作一个结构体node表示，每个节点中，需要去和别的区间合并的信息我们开结构体info，所以重载+号就是为了两个子区间信息的合并。最后query只需要返回info即可，只有里面有我们需要的信息

#include <bits/stdc++.h>
using namespace std;
#define endl '\n'
#define Acode ios::sync_with_stdio(false), cin.tie(0), cout.tie(0)
#define int long long
const int N = 2e5 + 10;
int a[N], n;
// 左儿子为2*id，右儿子为2*id+1
// 左儿子区间为[l,mid] ,右儿子为[mid+1,r]

struct info
{
    int miv;
    int cnt;
};

struct node
{
    info val;
} seg[N << 2];

info operator+(const info &a, const info &b)
{
    info c;
    c.miv = min(a.miv, b.miv);
    if (a.miv == b.miv)
        c.cnt = a.cnt + b.cnt;
    else if (a.miv < b.miv)
        c.cnt = a.cnt;
    else
        c.cnt = b.cnt;
    return c;
}

void up(int id)
{
    seg[id].val = seg[id << 1].val + seg[id << 1 | 1].val;
}

void build(int id, int l, int r) // id代表区间节点标号，l,r代表该区间节点的左右端点
{
    if (l == r)
    {
        seg[id].val = {a[l], 1};
        return;
    }
    int mid = l + r >> 1;
    build(id << 1, l, mid);
    build(id << 1 | 1, mid + 1, r);
    up(id);
}

void change(int id, int l, int r, int x, int val)
{
    if (l == r)
    {
        seg[id].val = {val, 1};
        return;
    }
    int mid = l + r >> 1;
    if (x <= mid)
        change(id << 1, l, mid, x, val);
    else
        change(id << 1 | 1, mid + 1, r, x, val);
    up(id);
}

info query(int id, int l, int r, int ql, int qr)
{
    if (ql <= l && r <= qr)
        return seg[id].val;
    int mid = l + r >> 1;
    if (qr <= mid)   // 同理，查询区间属于左儿子就向左边去找 ,反之是右儿子
        return query(id << 1, l, mid, ql, qr);
    else if (ql > mid)
        return query(id << 1 | 1, mid + 1, r, ql, qr);
    else
        return query(id << 1, l, mid, ql, qr) + query(id << 1 | 1, mid + 1, r, ql, qr);
}

void solve()
{
    int q;
    cin >> n >> q;
    for (int i = 1; i <= n; i++)
        cin >> a[i];
    build(1, 1, n);
    while (q--)
    {
        // cerr << "TTTT\n";
        int op;
        cin >> op;
        if (op == 1)
        {
            int x, d;
            cin >> x >> d;
            change(1, 1, n, x, d);
        }
        else
        {
            int l, r;
            cin >> l >> r;
            auto ans = query(1, 1, n, l, r);
            cout << ans.miv << " " << ans.cnt << endl;
        }
    }
}

signed main()
{
    Acode;
    int T = 1;
    while (T--)
    {
        solve();
    }
    return 0;
}

线段树2

打标记分两步，首先是将这个区间的值改成正确的（为了之后的up），第二步是更新lazy标记

标记之间合并的之后，要考虑能否正确的下放上一层的标记！！

#include <bits/stdc++.h>
using namespace std;
#define endl '\n'
#define Acode ios::sync_with_stdio(false), cin.tie(0), cout.tie(0)
#define int long long
const int N = 2e5 + 10;
int a[N], n;

struct info
{
    int maxv;
};

struct node
{
    int lazy = 0;
    info val;
} seg[N << 2];

info operator+(const info &a, const info &b)
{
    info c;
    c.maxv = max(a.maxv, b.maxv);
    return c;
}

void up(int id) // up的时候lazy标记不用管，因为合并的两个区间的信息info是正确的
{
    seg[id].val = seg[id << 1].val + seg[id << 1 | 1].val;
}

void build(int id, int l, int r)
{
    seg[id].lazy = 0;
    if (l == r)
    {
        seg[id].val = {a[l]};
        return;
    }
    int mid = l + r >> 1;
    build(id << 1, l, mid);
    build(id << 1 | 1, mid + 1, r);
    up(id);
}

void settag(int id, int l, int r, int x) // 真正的区间修改函数
{
    seg[id].lazy += x;
    seg[id].val.maxv += x;
}

void down(int id, int l, int r) // down就是对底下的两个区间进行区间修改，直接用settag函数即可
{
    if (!seg[id].lazy)
        return;
    int mid = l + r >> 1;
    settag(id << 1, l, mid, seg[id].lazy);
    settag(id << 1 | 1, mid + 1, r, seg[id].lazy);
    seg[id].lazy = 0;
}

void modify(int id, int l, int r, int ql, int qr, int x)
{
    if (l > qr || r < ql)
        return;
    if (ql <= l && r <= qr)
    {
        settag(id, l, r, x);
        return;
    }
    int mid = l + r >> 1;
    down(id, l, r);
    modify(id << 1, l, mid, ql, qr, x);
    modify(id << 1 | 1, mid + 1, r, ql, qr, x);
    up(id);
}

info query(int id, int l, int r, int ql, int qr)
{
    if (ql <= l && r <= qr)
        return seg[id].val;
    int mid = l + r >> 1;
    down(id, l, r);
    if (qr <= mid)
        return query(id << 1, l, mid, ql, qr);
    else if (ql > mid)
        return query(id << 1 | 1, mid + 1, r, ql, qr);
    else
        return query(id << 1, l, mid, ql, qr) + query(id << 1 | 1, mid + 1, r, ql, qr);
}

void solve()
{
    int q;
    cin >> n >> q;
    for (int i = 1; i <= n; i++)
        cin >> a[i];
    build(1, 1, n);
    while (q--)
    {
        // cerr << "TTTT\n";
        int op;
        cin >> op;
        if (op == 1)
        {
            int l, r, d;
            cin >> l >> r >> d;
            modify(1, 1, n, l, r, d);
        }
        else
        {
            int l, r;
            cin >> l >> r;
            auto ans = query(1, 1, n, l, r);
            cout << ans.maxv << endl;
        }
    }
}

线段树上二分(一个log)

q次询问求一段区间内第一个大于等于d的数的下标，找不到返回-1

#include <bits/stdc++.h>
using namespace std;
#define endl '\n'
#define Acode ios::sync_with_stdio(false), cin.tie(0), cout.tie(0)
#define int long long
const int N = 2e5 + 10;
int a[N], n;

struct info
{
    int maxv;
};

struct node
{
    info val;
} seg[N << 2];

info operator+(const info &a, const info &b)
{
    info c;
    c.maxv = max(a.maxv, b.maxv);
    return c;
}

void up(int id) // up的时候lazy标记不用管，因为合并的两个区间的信息info是正确的
{
    seg[id].val = seg[id << 1].val + seg[id << 1 | 1].val;
}

void build(int id, int l, int r)
{
    if (l == r)
    {
        seg[id].val = {a[l]};
        return;
    }
    int mid = l + r >> 1;
    build(id << 1, l, mid);
    build(id << 1 | 1, mid + 1, r);
    up(id);
}

void change(int id, int l, int r, int x, int w)
{
    if (l == r)
    {
        seg[id].val.maxv = w;
        return;
    }
    int mid = l + r >> 1;
    if (x <= mid)
        change(id << 1, l, mid, x, w);
    else
        change(id << 1 | 1, mid + 1, r, x, w);
    up(id);
}

int search(int id, int l, int r, int ql, int qr, int d)  
{
    if (ql == l && r == qr)  //如果查询区间等于当前区间了
    {
        if (seg[id].val.maxv < d)
            return -1;
        else
        {
            if (l == r)   //最终递归结束条件，就是只有一个数了，那么下标就是它
                return l;
            int mid = l + r >> 1;
            if (seg[id << 1].val.maxv >= d)
                return search(id << 1, l, mid, ql, mid, d);
            else
                return search(id << 1 | 1, mid + 1, r, mid + 1, qr, d);
        }
    }
    int mid = l + r >> 1;

    if (qr <= mid)
        return search(id << 1, l, mid, ql, qr, d);
    else if (ql > mid)
        return search(id << 1 | 1, mid + 1, r, ql, qr, d);
    else
    {
        int pos = search(id << 1, l, mid, ql, mid, d);  //先优先查看左边下标小的区间有没有符合的
        if (pos == -1)
            return search(id << 1 | 1, mid + 1, r, mid + 1, qr, d); //左边没有再选择右边
        else
            return pos;
    }
}

void solve()
{
    int q;
    cin >> n >> q;
    for (int i = 1; i <= n; i++)
        cin >> a[i];
    build(1, 1, n);
    while (q--)
    {
        // cerr << "TTTT\n";
        int op;
        cin >> op;
        if (op == 1)
        {
            int x, d;
            cin >> x >> d;
            change(1, 1, n, x, d);
        }
        else
        {
            int l, r, d;
            cin >> l >> r >> d;
            cout << search(1, 1, n, l, r, d) << endl;
        }
    }
}