首页 > 其他分享 >Codeforces Round #449 (Div. 1) C Willem, Chtholly and Seniorious

Codeforces Round #449 (Div. 1) C Willem, Chtholly and Seniorious

时间:2022-11-23 13:11:36浏览次数:85  
标签:Willem Chtholly 449 int ll itl split ans now

Willem, Chtholly and Seniorious

珂朵莉树

慕名而来

操作 \(3\) 直接排序是我没想到的,因为随机数据所以才能过吧

\(split\) 操作中忘了开 \(longlong\),\(wa3\)

#include <iostream>
#include <cstdio>
#include <set>
#include <vector>
#include <algorithm>
using namespace std;
typedef long long ll;
#define pll pair<ll, ll>
#define It set<ran>::iterator

ll qpow(ll x, ll n, ll mod)
{
    ll ans = 1;
    x %= mod;
    while(n)
    {
        if(n & 1) ans = ans * x % mod;
        n >>= 1;
        x = x * x % mod;
    }
    return ans % mod;
}

struct ran
{
    int l, r;
    mutable ll v;
    ran(){}
    ran(int _l, int _r, ll _v)
    {
        l = _l;
        r = _r;
        v = _v;
    }
    bool operator < (const ran &x) const
    {
        return l < x.l;
    }
};

set<ran>st;
It split(int pos)
{
    It now = st.lower_bound(ran(pos, -1, 0));
    if(now != st.end() && now->l == pos) return now;
    now--;
    ll l = now->l, r = now->r, v = now->v;
    st.erase(now);
    st.insert(ran(l, pos - 1, v));
    return st.insert(ran(pos, r, v)).first;
}

void add(int l, int r, ll v)
{
    It itr = split(r + 1);
    It itl = split(l);
    for(It it=itl; it!=itr; it++)
        it->v += v;
}

void merge_update(int l, int r, ll v)
{
    It itr = split(r + 1), itl = split(l);
    st.erase(itl, itr);
    st.insert(ran(l, r, v));
}

ll query_4(int l, int r, ll x, ll y)
{
    ll ans = 0;
    It itr = split(r + 1), itl = split(l);
    for(; itl!=itr; itl++)
        ans = (ans + qpow(itl->v, x, y) * (itl->r - itl->l + 1)) % y;
    return ans;
}

ll query_kth(int l, int r, ll x)
{
    It itr = split(r + 1), itl = split(l);
    vector<pll>temp;
    while(itl != itr)
    {
        temp.push_back(make_pair(itl->v, itl->r - itl->l + 1));
        itl++;
    }
    sort(temp.begin(), temp.end());
    ll ans = 0;
    for(int i=0; i<temp.size() && x>0; i++)
    {
        ans = temp[i].first;
        x -= temp[i].second;
    }
    return ans;
}

ll seed = 0, vmax = 0;
ll rnd()
{
    ll ret = seed;
    seed = (seed * 7 + 13) % 1000000007;
    return ret;
}

int main()
{
    ios::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
    int n, m;
    cin >> n >> m >> seed >> vmax;
    vector<ll>a(n + 2, -1);
    // for(int i=1; i<=n; i++) a[i] = 1e9;
    for(int i=1; i<=n; i++) a[i] = rnd() % vmax + 1;
    // for(int i=1; i<=n; i++) cout << a[i] << " ";
    // cout << "\n";
    for(int i=1; i<=n; i++)
    {
        if(a[i] == a[i - 1]) continue;
        int j = i;
        while(a[j] == a[i]) j++;
        st.insert(ran(i, j - 1, a[i]));
    }
    ll op = 0, l = 0, r = 0;
    while(m--)
    {
        op = rnd() % 4 + 1;
        l = rnd() % n + 1;
        r = rnd() % n + 1;
        if(l > r) swap(l, r);
        ll x = 0, y = 0;
        if(op == 3) x = rnd() % (r - l + 1) + 1;
        else x = rnd() % vmax + 1;
        if(op == 4) y = rnd() % vmax + 1;
        // cout << op << " " << l << " " << r << " " << x << " " << y << "\n";
        if(op == 1) add(l, r, x);
        else if(op == 2) merge_update(l, r, x);
        else if(op == 3) cout << query_kth(l, r, x) << "\n";
        else cout << query_4(l, r, x, y) << "\n";
    }
    // cout << endl;
    return 0;
}

标签:Willem,Chtholly,449,int,ll,itl,split,ans,now
From: https://www.cnblogs.com/dgsvygd/p/16917946.html

相关文章

  • Codeforces897B-Chtholly's request
    B.Chtholly'srequesttimelimitpertestmemorylimitpertestinputoutput—Thanksalotfortoday.—Iexperien......
  • 困难-2449. 使数组相似的最少操作次数
    给你两个正整数数组 nums和 target ,两个数组长度相等。在一次操作中,你可以选择两个不同 的下标 i和 j ,其中 0<=i,j<nums.length ,并且:令 nums[i]=num......
  • ACWing - 4493 -- 思维题&&并查集&&dfs
    题目描述环形连通分量思路对于一个无向图中的简单环(环中边的数量等于点的数量),有一个很强的性质:每个点的度数等于\(2\)。那么我们只需要先找出所有的连通块,然后判......
  • 【镜像下载】大更新:Windows 11 (22449.1000 / 22000.176) 八合一纯净版
    今天凌晨,微软照例向Beta和Dev通道的 Windows 预览体验用户推送了本周Windows11预览版的更新,和上几周不同的是,本次向 Beta 和 Dev通道推送的是不同的版本:Beta......
  • 解决mysql 1449 问题
    现象:数据库可以连接,重启也正常启动。但查询数据库时,就是报下面的错误报错:Theuserspecifiedasadefiner(‘mysql.infoschema’@‘localhost’)doesnotexists查看m......
  • Willemijn 如何将职业生涯从营销转向 Web 开发和网络安全
    Willemijn如何将职业生涯从营销转向Web开发和网络安全转行是个人发展的重要一步。但是两次转换职业需要巨大的热情和承诺。这正是我们的毕业生WillemijnWaterbolk......
  • CF896C Willem, Chtholly and Seniorious
    写一种数据结构,支持:\(1\)\(l\)\(r\)\(x\):将\([l,r]\)区间所有数加上\(x\)\(2\)\(l\)\(r\)\(x\):将\([l,r]\)区间所有数改成\(x\)\(3\)\(l\)\(r\)\(x\):输......
  • CF896E Welcome home, Chtholly
    题面维护一个\(n(n\leqslant100000)\)个元素序列\(a_1,a_2,\dots,a_n\),有\(m(m\leqslant100000)\)次操作,分为如下两种。给定\(l,r,x\),将\(a_l,a_{l+1},\dots,a_r\)中......