icontofig | 发布于 2020-01-15 19:57:24 | 阅读量 977 | 思维题 树状数组
发布于 2020-01-15 19:57:24 | 思维题 树状数组

题目大意

一开始有一个初始顺序的排列[1,n],一共有m次操作,每次将数ai从序列中取出,放到最开头的位置生成一个新的排列。

求问在所有过程中每一个数最小的下标位置和最大的下标位置。

题解

最小的下标位置是非常容易求得的,这很明显,因为如果从来没有被放到开头,那么答案一定是i,否则答案就是1。

需要思考的点在于求最大的下标位置。

这个数据范围不允许进行模拟,链表也不行(链表的单个操作、查询效率极差)。

先来考虑一种特殊情况1:

假设当前所有的数字都已经被放置到第一位过了,在满足这种条件后的最大的下标位置怎么求。

明显元素之间一开始的位置在哪里已经完全互不影响了。

如果一个数再被要求放到第一位,那么这个操作之前的下标位置可能就会影响答案。

而这个下标位置是什么?我们想什么样的操作会影响这个下标位置。很明显只有在上一次此数被放到第一位的时间之后,不同的数字放置到第一位才会使得这个数字的位置向后推移。也就是说,这个下标位置,就是当前未操作时刻和上一次这个数被放到第一位以后的时刻,这之间的不同数字的个数再+1,也就是区间内不同数的个数。

树状数组可以离线询问区间内不同数的个数。由于这道题的特殊性,我们无需对询问区间进行右端点优先排序,直接操作查询即可。

然后再考虑剩下的情况2:

如果一个数之前没有被放置在第一位的经历该如何计算?

这样在它被第一次放置到第一位的命令执行以前,其最大下标位置是之前的时刻被放置在第一位的大于此数的数字的个数 + 此数最初的坐标值。问题变成了维护区间内出现的不同数字的个数,需要用另外一个树状数组进行维护,只需要再每个数字第一次被放置在第一位时维护一次,查询一次即可。

在问题的最后,这样不一定已经求得最大值,因为对于每一个数字,最后可能有影响到最大值的问题但是没有查询更新。

所以在最后我们就要:

对于在操作序列中出现过的数字,我们执行情况1的查询一次。

对于未在操作序列中出现过的数字,我们执行情况2的查询一次。

代码

#include <bits/stdc++.h>
const int maxn = 3e5+5;
using namespace std;
map<int,int>mp;
int tr[maxn],a[maxn],ans[maxn],c[maxn];
int n,m;
int lowbit(int x){
	return x & (-x);
}
void add(int x,int val){
	while(x <= m){
		tr[x] += val;
		x += lowbit(x);
	}
    return;
}
int sol(int x){
	int res = 0;
	while(x){
		res += tr[x];
		x -= lowbit(x);
	}
	return res;
}
void add2(int x,int val){
    while(x <= n){
        c[x] += val;
        x += lowbit(x);
    }
    return;
}
int sum(int x){
    int res = 0;
    while(x){
        res += c[x];
        x -= lowbit(x);
    }
    return res;
}
int mx[maxn],mn[maxn];
int main(){	
    scanf("%d %d",&n,&m);
    for(int i = 1;i <= n;++i){
        mx[i] = mn[i] = i;
    }
    for(int i = 1;i <= m;i++){
        scanf("%d",&a[i]);
        mn[a[i]] = 1;
    }
    mp.clear();
    for(int i = 1;i <= m;++i){
        int now = a[i];
        if(!mp[now]){
            add(i,1);
            mp[now] = i;
            add2(now,1);
            mx[now] += sum(n) - sum(now);
        }
        else{
            add(mp[now],-1);
            add(i,1);
            mx[now] = max(sol(i-1) - sol(mp[now]) + 1,mx[now]);
            mp[now] = i;
        }
    }
    for(int i = 1;i <= n;++i){
        if(!mp[i]){
            mx[i] += sum(n) - sum(i);
        }
        else mx[i] = max(mx[i],sol(m) - sol(mp[i]) + 1);
    }
    for(int i = 1;i <= n;++i){
        printf("%d %d\n",mn[i],mx[i]);
    }
	return 0;
}



内容更新于: 2020-01-15 19:57:31
链接地址: http://blog.leanote.com/post/icontofig/b546d6e423ff

上一篇: 一个看起来飞快的AC自动机模板

下一篇: HDU 2457 DNA Repair AC自动机 DP

977 人读过
立即登录, 发表评论.
没有帐号? 立即注册
0 条评论
文档导航