首页 > 其他分享 >「杂题乱刷2」CF1288E

「杂题乱刷2」CF1288E

时间:2024-11-11 20:18:36浏览次数:1  
标签:forl pos CF1288E add query 杂题 define

题目链接

CF1288E Messenger Simulator

解题思路

发现向前移的部分普通维护比较困难,因此我们考虑通过某种方式来维护这个东西。

考虑建立 \(m\) 个虚点来维护,每次询问都将实点移至虚点去。这里求答案我们需要支持单点加,区间求和,可以用树状数组轻松维护。

参考代码

#include<bits/stdc++.h>
using namespace std;
//#define map unordered_map
#define re register
#define ll long long
#define forl(i,a,b) for(re ll (i)=(a);i<=(b);(i)++)
#define forr(i,a,b) for(re ll (i)=(a);i>=(b);(i)--)
#define pii pair<ll,ll>
#define mid ((l+r)>>1)
#define lowbit(x) (x&-x)
#define pb push_back
#define IOS ios::sync_with_stdio(0),cin.tie(0),cout.tie(0);
#define endl '\n'
#define QwQ return 0;
template<typename T1,typename T2>bool Max(T1&x,T2 y){if(y>x)return x=y,1;return 0;}
template<typename T1,typename T2>bool Min(T1&x,T2 y){if(y<x)return x=y,1;return 0;}
ll _t_;
void _clear(){}
ll n,m;
ll pos[1000010];
ll q[1000010];
ll tree[1000010];
ll last;
ll ans1[1000010],ans2[1000010];
void add(ll x,ll y)
{
    if(x==0)
        return ;
    for(;x<=1e6+5;x+=lowbit(x))
        tree[x]+=y;
}
ll query(ll x)
{
    ll sum=0;
    for(;x;x-=lowbit(x))
        sum+=tree[x];
    return sum;
}
void solve()
{
    _clear();
    cin>>n>>m;
    last=m;
    forl(i,1,m)
        cin>>q[i];
    forl(i,1,n)
        pos[i]=m+i;
    forl(i,1,n)
        ans1[i]=ans2[i]=i;
    forl(i,1,n)
        add(pos[i],1);
    forl(i,1,m)
    {
        Max(ans2[q[i]],query(pos[q[i]]));
        add(pos[q[i]],-1);
        pos[q[i]]=last--;
        ans1[q[i]]=1;
        add(pos[q[i]],1);
    }
    forl(i,1,n)
        Min(ans1[i],query(pos[i])),
        Max(ans2[i],query(pos[i]));
    forl(i,1,n)
        cout<<ans1[i]<<' '<<ans2[i]<<endl;
}
int main()
{
//    freopen("tst.txt","r",stdin);
//    freopen("sans.txt","w",stdout);
    IOS;
    _t_=1;
//    cin>>_t_;
    while(_t_--)
        solve();
    QwQ;
}

标签:forl,pos,CF1288E,add,query,杂题,define
From: https://www.cnblogs.com/wangmarui/p/18540501

相关文章

  • 「杂题乱刷2」CF1219G
    题目链接CF1219GHarvester解题思路就是个嗯分讨题。发现最终选择的方案总共就以下五种情况:选\(4\)行\(0\)列。选\(3\)行\(1\)列。选\(2\)行\(2\)列。选\(1\)行\(3\)列。选\(0\)行\(4\)列。对于第一,五种情况,直接取每行或每列的前四大值......
  • 「杂题乱刷2」CF1354E
    题目链接CF1354EGraphColoring(*2100)解题思路发现这个东西就是类似于二分图染色的东西。因为\(2\)只能和\(1,3\)链接。其余种类的点都不能连接。不妨把\(1,3\)都看成同一个点放到最后处理。那么我们就相当于是要找到一种方案使得选择每个联通快的黑点或白点,使得最......
  • 「杂题乱刷2」CF1370F2
    题目链接CF1370F2TheHiddenPair(HardVersion)(*2700)题目描述真的很难吗?我们首先考虑找出第一个特殊点。我们可以先求出这两个点路径中的任意一个点。发现询问\(1\simn\)就使我们需要的询问、接下来以这个路径中的一个点为根来确定每个节点的深度。接下来考虑二......
  • 并查集+最小生成树 学习笔记+杂题 1
    图论系列:前言:相关题单:戳我算法讲解:戳我代码可能过多啊,到时候页面别卡死了,所以就把代码最前面的缺省源删了(反正就是几个头文件/defineintlonglong,自己加一下即可)。并查集记得初始化,最小生成树记得排序。P3367【模板】并查集板子题,给定\(n\)个元素,有2种操作,一种合并,......
  • 「杂题乱刷2」P11267
    题目链接P11267【MX-S5-T1】王国边缘解题思路先考虑对于\(1\simn\)中的每一个点往后跳\(1\)次会跳的距离。那么为什么只用处理\(1\simn\)这些点而不去处理其余的点往后跳的距离呢?我们可以发现,由于字符串是无线循环的,所以对于位置模\(n\)的结果相同时,那么往后跳......
  • 双连通分量学习笔记+杂题
    图论系列:前言:もしも明日がくるのならあなたと花を育てたいもしも明日がくるのならあなたと愛を語りたい走って笑って転んで相关题单:https://www.luogu.com.cn/training/641352一.割点与桥双连通分量是针对无向图来说的,有向图是强连通分量。在了解双连通分量之前需要先......
  • AGC 杂题
    AGC029CLexicographicconstraints有\(n\)个字符串,现在告知它们的长度\(a_i\),求使得\(\foralli\in[1,n),s_i<s_{i+1}\)的最小字符集大小。\(n\le2\times10^5,a_i\le10^9\)二分字符集大小\(|\Sigma|\),分类讨论,设起始字符为a:\(a_i<a_{i+1}\):显然\(s_{i+1}\leftarr......
  • ABC 杂题
    ABC186EThrone有\(n\)个圆形排列的椅子,一开始你在\(s+1\)上,每次可以向右移动\(k\)个位置,求移动到\(1\)的最小步数,或报告无解。\(2\len,k\le10^9\)很容易想到构造方程:\[s+qk\equiv0\pmodn\]\[q\equiv(n-s)k^{-1}\pmodn\]直接exgcd求逆元,算出在\([1,n-1]\)......
  • 杂题选做1
    杂题选做1[ARC112F]DieSiedler注意到如果存在某一个\(j\)满足这种牌的数量大于等于\(2j\),那么一定会兑换为\(j\bmodn+1\)的牌。所以我们考虑这个过程的逆过程,就是将一张牌\(j\)换成\((j-1)!2^{j-1}\)张\(1\)号牌,最终全部的牌都被转化为了\(1\)号牌,但是结果并......
  • 数据结构杂题乱记
    由于是杂题乱记所以题目大多数不会太难。目录P2572[SCOI2010]序列操作题目内容思路代码P2572[SCOI2010]序列操作题目内容给你一个\(01\)序列,支持\(5\)种操作:0lr区间赋值为\(0\);1lr区间赋值为\(1\);2lr区间取反,即\(0\)变\(1\)、\(1\)变\(0\);3lr询......