2016-2017ACM-ICPC东北欧区域赛（NEERC16）Gym101190E：离线查询与排序优化策略

题目链接&＃xff1a;http://codeforces.com/gym/101190/attachments

题意&＃xff1a;一个公共三轮车车站可以提供给一些人租车&＃xff0c;但是在开始时刻&＃xff0c;公园里有所少量车这个是不确定的&＃xff0c;然后现在有n个信息和q个询问&＃xff0c;信息有两种形式&＃43; a b代表在a时间有b个人还车&＃xff0c;另外一种是 - a b代表在a时间有b个人借车&＃xff0c;这些人借车是要排队的&＃xff0c;如果当前没有车&＃xff0c;则只能等待&＃xff0c;对于每一个询问给定了初始时刻车站里面有多少量车&＃xff0c;然后要询问的是对于每一个可能的初始值的等待时间&＃xff0c;如果等待时间是不确定的话&＃xff0c;输出INFINITY。

解法&＃xff1a;首先是一个单点更新的问题&＃xff0c;可是我们发现一次更新之后会影响下一次的查询&＃xff0c;或者你更新之后又可以回到之前的版本&＃xff0c;所以可持久化&＃xff1f;瞎几把yy之后&＃xff0c;我们不妨来分析一下样例&＃xff0c;可以观察到什么时候是要租车的呢&＃xff1f;首先输入的信息用 op t[i] a[i]来表示一下&＃xff0c;t[i]代表时间戳&＃xff0c;a[i]代表人或者车的数量(取决于操作)&＃xff0c;第二种操作意味着要减少a[i]量车&＃xff0c;如果车你的数量减小到<&＃61;0那么久只能等待了。并且当前要等待的时间是多少呢&＃xff1f;我们容易把它预处理出来&＃xff0c;下面的s[i]就是人或者车的数量的前缀和&＃xff0c;显然为正代表当前时间不需要租车&＃xff0c;否则需要租车。

for(int i &＃61; 1; i <&＃61; n; i&＃43;&＃43;){s[i] &＃61; s[i-1] &＃43; a[i];if(i 1] - t[i];}

处理出这个也不能解决这个问题&＃xff0c;接下来显然当s[i]>0的那些时间段是不用考虑的&＃xff0c;你想啊&＃xff0c;当前车的数量够用&＃xff0c;肯定傻子才会等待吧。所以我们把需要等待的总时间以及等待的时间段的长度记录下来

long long sum1 &＃61; 0, sum2 &＃61; 0;for(int i &＃61; 1; i <&＃61; n; i&＃43;&＃43;){if(s[i] <0){b[&＃43;&＃43;cnt] &＃61; i;sum1 &＃43;&＃61; 1LL*(-s[i])*t[i];sum2 &＃43;&＃61; t[i];}}

接下来就是想到我们在线很难做那么我们可以离线做啊&＃xff0c;所以就有了询问离线的思路了。我们会想离线该怎么做呢&＃xff1f;容易想到我们会按照x来排序&＃xff0c;离线是为了能用到之前处理的信息&＃xff0c;而不是无序重来一遍&＃xff0c;这样显然是可以降低复杂度的吧。所以我们会想到按照x从小到大排序&＃xff0c;这里的x就是第初始的车的数量&＃xff0c;想一下吧&＃xff0c;当前x比较小的时候你覆盖了一些之前等待的时间区间&＃xff0c;那么下次你的x比现在的大&＃xff0c;也必然可以覆盖上次的区间&＃xff0c;所以就不用重复扫描&＃xff0c;自然大大降低了复杂度。

struct node{int x, id;bool operator <(const node &rhs) const{return x }c[maxn];

在询问离线的时候我已经提到了&＃xff0c;要利用之前的信息&＃xff0c;所以我们也要对那些需要等待的时间段进行排序&＃xff0c;每一个时间段都有一个值代表当前等待的人数&＃xff0c;这里是负数所以从大到小排&＃xff0c;比如-2>-3&＃xff0c;那么2会排在3的前面&＃xff0c;那么你x增大&＃xff0c;显然也是可以覆盖当前区间能覆盖的每一条线段的&＃xff0c;然后我们按照这个思路去模拟一发就可以了。注意不确定的条件就是当当前的x&＃43;s[n]<0的时候&＃xff0c;这个时候显然车都不够。

sort(c &＃43; 1, c &＃43; q &＃43; 1);for(int i &＃61; 1; i <&＃61; q; i&＃43;&＃43;){int x &＃61; c[i].x;while(j <&＃61; cnt && (-s[b[j]]) <&＃61; x){sum1 -&＃61; 1LL*(-s[b[j]]) * t[b[j]];sum2 -&＃61; t[b[j]];&＃43;&＃43;j;}if(s[n] &＃43; x <0){ans[c[i].id] &＃61; -1;}else{ans[c[i].id] &＃61; sum1 - x * sum2;}}

完整码&＃xff1a;

#include
using namespace std;
const int maxn &＃61; 1e5 &＃43; 7;
int n, q;
int a[maxn], t[maxn];
int s[maxn];
int b[maxn], cnt;
long long ans[maxn];
struct node{int x, id;bool operator <(const node &rhs) const{return x }c[maxn];
bool cmp(int i, int j){return s[i] > s[j];
}int main()
{freopen("expect.in", "r", stdin);freopen("expect.out", "w", stdout);scanf("%d%d", &n, &q);for(int i &＃61; 1; i <&＃61; n; i&＃43;&＃43;){char op[5];scanf("%s%d%d", op, &t[i], &a[i]);if(op[0] &＃61;&＃61; &＃39;-&＃39;) a[i] &＃61; -a[i];}//处理出初始的信息for(int i &＃61; 1; i <&＃61; n; i&＃43;&＃43;){s[i] &＃61; s[i-1] &＃43; a[i];if(i 1] - t[i];}
// for(int i &＃61; 1; i <&＃61; n; i&＃43;&＃43;){
// printf("s[%d] &＃61; %d, t[%d] &＃61; %d\n", i, s[i], i, t[i]);
// }long long sum1 &＃61; 0, sum2 &＃61; 0;for(int i &＃61; 1; i <&＃61; n; i&＃43;&＃43;){if(s[i] <0){b[&＃43;&＃43;cnt] &＃61; i;sum1 &＃43;&＃61; 1LL*(-s[i])*t[i];sum2 &＃43;&＃61; t[i];}}sort(b &＃43; 1, b &＃43; cnt &＃43; 1, cmp);int j &＃61; 1;long long k &＃61; 0;for(int i &＃61; 1; i <&＃61; q; i&＃43;&＃43;){scanf("%d", &c[i].x);c[i].id &＃61; i;}sort(c &＃43; 1, c &＃43; q &＃43; 1);for(int i &＃61; 1; i <&＃61; q; i&＃43;&＃43;){int x &＃61; c[i].x;while(j <&＃61; cnt && (-s[b[j]]) <&＃61; x){sum1 -&＃61; 1LL*(-s[b[j]]) * t[b[j]];sum2 -&＃61; t[b[j]];&＃43;&＃43;j;}if(s[n] &＃43; x <0){ans[c[i].id] &＃61; -1;}else{ans[c[i].id] &＃61; sum1 - x * sum2;}}for(int i &＃61; 1; i <&＃61; q; i&＃43;&＃43;){if(ans[i] &＃61;&＃61; -1) printf("INFINITY\n");else printf("%lld\n", ans[i]);}return 0;
}