【Educational Codeforces Round 80(div2)】E-Messenger Simulator (树状数组)
程序员文章站
2022-06-04 18:14:55
...
一、题目链接
https://codeforces.com/contest/1288/problem/E
二、题意
读入整数n、m以及m次操作。
起初,数列中为整数1~n按升序排列,对应位置1~n。每次操作读入,将数列中的移动到数列最前面,更新数列内所有数位置。求执行完所有操作后,1~n每个整数在操作过程中位置的最大值和最小值。
三、数据范围
1 ≤ n, m ≤ 3 *
1 ≤ ≤ n
四、解题思路
首先,对每次操作,暴力循环更新位置肯定是行不通的。如何对这一步进行优化?
怎么把指定数字向前移动?
很容易想到在原数列前增加m个空位,每次操作把从后往前放到那m个空位里,更新的最小位置为1,把原位置清除。
怎么更新其他数字的位置?
没有被操作的数不必移动。开一个长m+n的数列e,把有元素的位置记为1,没有元素的位置记为0,(初始e[1]~e[m]=0,e[m+1]~e[m+n]=1)每次操作进行两个修改:原位置变成0,新位置变成1,那么每个数的位置其实就是求该位置前有多少个”1“,即该位置的前缀和。
怎么快捷地修改、查询前缀和?
树状数组。:happy: (←这是俺新学的Typora表达式~)
二进制索引数,可以在O()时间轻松搞定~~其存储思路如下:
(百度百科偷的图,A为需要求前缀和的数列,C为树状数组的储存思路)
代码中,lowbit、add、sum函数均源于树状数组模板,在此不做赘述。
五、AC代码
#include <bits/stdc++.h>
using namespace std;
const int MAXN = 7e5 + 10; //是m+n,maxn要开两倍!!!
int n, m, pos[MAXN], e[MAXN], maxx[MAXN], minx[MAXN];
int lowbit(int x) //x的二进制表达式中最低位的1所对应的值
{
return x & (-x);
}
int add(int x, int v) //修改前缀和
{
while(x < MAXN)
{
e[x] += v;
x += lowbit(x);
}
}
int sum(int x) //查询前缀和
{
int re = 0;
while(x > 0)
{
re += e[x];
x -= lowbit(x);
}
return re;
}
int main()
{
cin >> n >> m;
for (int i = 1; i <= n; i++) //初始化
{
pos[i] = i + m; //在数列前腾出m个空格,所以位置暂时往后移m个
add(pos[i], 1); //此位置上元素+1
maxx[i] = i; //初始化i的最大、最小位置
minx[i] = i;
}
for (int i = 1; i <= m; i++)
{
int x;
cin >> x;
maxx[x] = max(maxx[x], sum(pos[x])); //更新位置最大值
minx[x] = 1; //更新位置最小值
add(pos[x], -1); //删除原位置上的数
pos[x] = m - i + 1; //把x放到前面的空格中
add(pos[x], 1); //新位置上元素+1
}
for (int i = 1; i <= n; i++)
{
maxx[i] = max(maxx[i], sum(pos[i]));
//操作中没有移动的数位置肯定越来越大,所以在所有结束后统一更新
cout << minx[i] << ' ' << maxx[i] << endl;
}
return 0;
}