头像

cht

Acwing菜鸡博主,喜欢点个关注吧~(会互粉)




离线:1天前


最近来访(2441)
用户头像
宋君婉
用户头像
马丁
用户头像
aWdw
用户头像
wangyc
用户头像
大学才
用户头像
_i_
用户头像
霍可乐
用户头像
IF_3
用户头像
你的老坛酸菜.
用户头像
zyz529
用户头像
封禁用户
用户头像
Heming
用户头像
OI
用户头像
Acwer
用户头像
人生如戏ba
用户头像
222222
用户头像
Toduring
用户头像
Oier12138
用户头像
7.9省赛加油
用户头像
acwing_3992

新鲜事 原文

cht
15天前
一个扫描线调一天


新鲜事 原文

cht
16天前
幸亏原来分享有存货,不然每个都得从头讲一遍。感觉原来的自己好励志啊。


新鲜事 原文

cht
16天前
A+B多种方法详解的坑好难填啊,况且代码都是自己写的,比较难弄hh


新鲜事 原文

cht
16天前
天梯有人玩吗


新鲜事 原文

cht
17天前
最近打算回顾一下之前的算法,参考https://www.acwing.com/solution/content/69403/写一个A+B每种算法的详解


新鲜事 原文

cht
19天前
无耻的捞一下( https://www.acwing.com/blog/content/21090/


活动打卡代码 AcWing 4269. 校庆

cht
19天前
//这里填你的代码^^
//注意代码要放在两组三个点之间,才可以正确显示代码高亮哦~

#include<bits/stdc++.h>
using namespace std;
int main()
{
    int n, m;
    cin >> n;
    char str[20];
    unordered_set<string> hash;
    while(n --)
    {
        scanf("%s", str);
        hash.insert(str);
    }
    cin >> m;
    string a, b;
    int cnt = 0;
    while(m --)
    {
        scanf("%s", str);
        string name = str;
        if(hash.count(name))
        {
            cnt ++;
            if(a.empty() || a.substr(6, 8) > name.substr(6, 8)) a = name;
        }
        if(b.empty() || b.substr(6, 8) > name.substr(6, 8)) b = name;
    }
    cout << cnt << endl;
    if(cnt) printf("%s\n", a.c_str());
    else printf("%s\n", b.c_str());
    return 0;
}



cht
21天前

首先感谢这位大佬对我的问题的回答!

不一定保证完全没有bug,有bug可以反馈一下我争取在下一个版本改

做题的时候不要用,很可能有bug!!!!而且可能不是最优化的

支持的操作:

区间修改

区间加法(2)

区间减法(3)

区间乘法(1)

区间查询

区间和(4)

区间最大值(5)

区间最小值(6)

单点查询及其应用

区间中位数(7)(不够完善,未进行小数的处理)

其他:对int以上取模(未完善,很多没有加上呢还)

#include<bits/stdc++.h>
using namespace std;
const int N = 1e6 + 10;
#define ll long long 
int n, p = INT_MAX, m;
int w[N];
struct Node
{
    int l, r;
    int add, sum, malt;
    int maxn, minn;
}tr[N * 4];
void pushup(int u)
{
    tr[u].sum = tr[u << 1].sum + tr[u << 1 | 1].sum;
    tr[u].sum = tr[u].sum % p;
    tr[u].maxn = max(tr[u << 1].maxn, tr[u << 1 | 1].maxn);
    tr[u].minn = min(tr[u << 1].minn, tr[u << 1 | 1].minn);
}
void pushdown(int u)
{
    tr[u << 1].maxn = tr[u << 1].maxn * tr[u].malt + tr[u].add;
    tr[u << 1].minn = tr[u << 1].minn * tr[u].malt + tr[u].add;
    tr[u << 1 | 1].maxn = tr[u << 1 | 1].maxn * tr[u].malt + tr[u].add;
    tr[u << 1 | 1].minn = tr[u << 1 | 1].minn * tr[u].malt + tr[u].add;
    tr[u << 1].sum = ((ll)tr[u << 1].sum * tr[u].malt + (ll)tr[u].add * (tr[u << 1].r - tr[u << 1].l + 1)) % p;
    tr[u << 1 | 1].sum = ((ll)tr[u << 1 | 1].sum * tr[u].malt + (ll) tr[u].add * (tr[u << 1 | 1].r - tr[u << 1 | 1].l + 1)) % p;
    tr[u << 1].add = ((ll)tr[u << 1].add * tr[u].malt + tr[u].add) % p;
    tr[u << 1 | 1].add = ((ll)tr[u << 1 | 1].add * tr[u].malt + tr[u].add) % p;
    tr[u << 1].malt = (ll)tr[u << 1].malt * tr[u].malt % p;
    tr[u << 1 | 1].malt = (ll)tr[u << 1 | 1].malt * tr[u].malt % p;
    tr[u].add = 0;
    tr[u].malt = 1;
}
void build(int u, int l, int r)
{
    if(l == r) tr[u] = {l, r, 0, w[r], 1, w[r], w[r]};
    else
    {
        tr[u] = {l, r, 0, 0, 1, 0, 0};
        int mid = (l + r) >> 1;
        build(u << 1, l, mid);
        build(u << 1 | 1, mid + 1, r);
        pushup(u);
    }
}
void change(int u, int l, int r, int malt, int add)
{
    if(tr[u].l >= l && tr[u].r <= r)
    {
        tr[u].maxn = tr[u].maxn * malt + add;
        tr[u].minn = tr[u].minn * malt + add;
        tr[u].sum = ((ll)tr[u].sum * malt + (ll)add * (tr[u].r - tr[u].l + 1)) % p;
        tr[u].add = ((ll)tr[u].add * malt + add) % p;
        tr[u].malt = (ll)tr[u].malt * malt % p;
    }
    else
    {
        pushdown(u);
        int mid = (tr[u].l + tr[u].r) >> 1;
        if(l <= mid) change(u << 1, l, r, malt, add);
        if(r > mid) change(u << 1 | 1, l, r, malt, add);
        pushup(u);
    }
}
int querysum(int u, int l, int r)
{
    if(tr[u].l >= l && tr[u].r <= r)
    {
        return tr[u].sum;
    }
    pushdown(u);
    int mid = (tr[u].l + tr[u].r) >> 1;
    ll res = 0;
    if(l <= mid) 
    {
        res += querysum(u << 1, l, r);
        res = res % p;
    }
    if(r > mid) 
    {
        res += querysum(u << 1 | 1, l, r);
        res = res % p;
    }
    return res;
}
double getmiddleidx(int l,int r)
{
    if((r - l + 1) % 2)
    {
        return querysum(1, (r - l) / 2 + 1, (r - l) / 2 + 1);
    }
    else
    {
        return querysum(1, (r - l + 1) / 2, (r - l + 1) / 2 + 1) / 2;
    }
}
int querymax(int u, int l, int r)
{
    if(tr[u].l >= l && tr[u].r <= r) return tr[u].maxn;
    pushdown(u);
    int mid = tr[u].l + tr[u].r >> 1;
    int v = 0;
    if(l <= mid) v = querymax(u << 1, l, r);
    if(r > mid) v = max(v, querymax(u << 1 | 1, l, r));
    return v;
} 
int querymin(int u, int l, int r)
{
    if(tr[u].l >= l && tr[u].r <= r) return tr[u].minn;
    pushdown(u);
    int mid = tr[u].l + tr[u].r >> 1;
    int w = 0x3f3f3f3f;
    if(l <= mid) w = querymin(u << 1, l, r);
    if(r > mid) w = min(w, querymin(u << 1 | 1, l, r));
    return w;
} 
int main()
{
    cin >> n;
    for(int i = 1; i <= n; i ++) cin >> w[i];
    build(1, 1, n);
    cin >> m;
    while(m --)
    {
        int op;
        int l, r;
        int c;
        cin >> op;
        if(op == 2)
        {
            cin >> l >> r >> c;
            change(1, l, r, 1, c);
        }
        else if(op == 1)
        {
            cin >> l >> r >> c;
            change(1, l, r, c, 0);
        }
        else if(op == 3) 
        {
            cin >> l >> r >> c;
            change(1, l, r, 1, -c);            
        }
        else if(op == 4)
        {
            cin >> l >> r;
            cout << querysum(1, l, r) << endl;
        }
        else if(op == 5)
        {
            cin >> l >> r;
            cout << querymax(1, l, r) << endl;            
        }
        else if(op == 6)
        {
            cin >> l >> r;
            cout << querymin(1, l, r) << endl;
        }
        else if(op == 7)
        {
            cin >> l >> r;
            cout << getmiddleidx(l, r) << endl;
        }
    }
    return 0;
}

挖坑时间到

后面争取先修好bug,然后加上求众数,把一个数弄成区间最小值的等等,有建议评论区见。




cht
21天前

回来弄线段树的时候,问一下:

线段树的懒标记和线段树内部的变量应该先更新哪个?还是都可以?为什么。



新鲜事 原文

cht
24天前
除了提高课那几个题各位dalao有没有什么线段树(不是可持久化的,可以带懒标记)的好题推荐啊