miku殿下11岁了呢，头图就选这个了。pid 64365538
先放题目Description
在大学期间，经常需要租借教室。大到院系举办活动，小到学习小组自习讨论，都需要向学校申请借教室。教室的大小功能不同，借教室人的身份不同，借教室的手续也不一样。
面对海量租借教室的信息，我们自然希望编程解决这个问题。我们需要处理接下来n天的借教室信息，其中第i天学校有ri个教室可供租借。共有m份订单，每份订单用三个正整数描述，分别为dj,sj,tj，表示某租借者需要从第sj天到第tj天租借教室（包括第sj天和第tj天），每天需要租借dj个教室。
我们假定，租借者对教室的大小、地点没有要求。即对于每份订单，我们只需要每天提供dj个教室，而它们具体是哪些教室，每天是否是相同的教室则不用考虑。借教室的原则是先到先得，也就是说我们要按照订单的先后顺序依次为每份订单分配教室。如果在分配的过程中遇到一份订单无法完全满足，则需要停止教室的分配，通知当前申请人修改订单。这里的无法满足指从第sj天到第tj天中有至少一天剩余的教室数量不足dj个。
现在我们需要知道，是否会有订单无法完全满足。如果有，需要通知哪一个申请人修改订单。
格式
输入格式
第一行包含两个正整数n,m，表示天数和订单的数量。
第二行包含n个正整数，其中第i个数为ri，表示第i天可用于租借的教室数量。
接下来有m行，每行包含三个正整数dj,sj,tj，表示租借的数量，租借开始、结束分别在第几天。
每行相邻的两个数之间均用一个空格隔开。天数与订单均用从1开始的整数编号。输出格式
如果所有订单均可满足，则输出只有一行，包含一个整数0。否则（订单无法完全满足）输出两行，第一行输出一个负整数-1，第二行输出需要修改订单的申请人编号。
样例
样例输入1
4 3 2 5 4 3 2 1 3 3 2 4 4 2 4样例输出1
-1 2限制
每个测试点1s
提示
对于10%的数据，有$1≤ n,m≤ 10$； 对于30%的数据，有$1≤ n,m≤1000$； 对于70%的数据，有$1≤ n,m≤ 10^5$； 对于100%的数据，有$1≤n,m≤10^6,0≤r_i,d_j≤10^9,1≤s_j≤t_j≤n$。
来源
Noip2012提高组复赛Day2T2
分析
对于这道题，我们可以直观的想到维护区间最小值，教室数少于0即无法满足该订单，那么直接暴力做法是可以拿30分的，但我们可以发现，随着订单数的增多，被用掉的教室数量肯定是只增不减的，也就是说，假设从第一个订单处理到第i个订单，我们发现教室数量都可以满足，那么，那个无法满足的订单，肯定是在第i天之后，即答案具有单调性，那么这个问题就可以转化为一个二分的问题，现在问题就变成如何快速判定从第一天到第i天的订单是否可以满足，考虑到只有判定需要用到我们维护的值，而模拟教室租借实际上只需要对区间进行更新，我们可以发现，实际上我们需要维护一个数组d[i]，代表第i天已经租借出去的教室数量，每模拟一个订单$(d,s,t)$,我们就在s到t上加上d，而判定即枚举一遍数组，判断改天租借出去的数量是否小于该天可供租借的数量，一旦出现某一天的d大于room,即$d[i]>room[i]$,则该订单无法满足，但直接在原数组上进行区间更新的复杂度是$O(mn)$的，这显然不能接受，考虑到我们只需要判定一次，而更新需要很多次，我们可以利用拆分的思想，令$c[i]=d[i]-d[i-1]$，则$d[i]=\sum_{i=1}^n(c[i])$,则区间更新变为$c[s]=c[s]+d,c[t+1]=c[t+1]-d$,这样一来，区间更新就变为$O(1)$了，复杂度就可以接受了，实测，速度较快。以下是代码：
//noip2012 borrow room;
#include<iostream>
#include<cstdio>
#include<cstring>
#define NN 1000000+1
using namespace std;
int d[NN],s[NN],t[NN],f[NN];
int n,m;
int room[NN];
bool test(int num){
memset(f,0,sizeof(f));
for(int i=1;i<=num;i++){
f[s[i]]+=d[i];
f[t[i]+1]-=d[i];
}
int a=0;
for(int i=1;i<=n;i++){
a+=f[i];
if(a>room[i]){
return false;
}
};
return true;
}
int main(){
ios::sync_with_stdio(false);
cin.tie(0);
cin >> n >> m;
for(int i=1;i<=n;i++){
cin >> room[i];
};
for(int i=1;i<=m;i++){
cin >> d[i] >> s[i] >> t[i];
};
int l=1,r=n+1;
int ans=0;
while(l<=r){
int mid=(l+r) >> 1;
if(test(mid)==true){
l=mid+1;
} else{
r=mid-1;
ans=mid;
}
};
if(ans==0){
cout << 0 << endl;
} else{
cout << -1 << endl<< ans << endl;
}
}在vijos的测试结果上还算可以接受。
但如果只是维护区间最小值的话，我们其实还有一种思路，每次处理完一遍订单后进行判定，而区间更新我们可以使用线段树解决，复杂度为$O(Nlog_2 M)$,但实际上，由于查询得太过频繁，普通线段树在最后几个点会被活活卡死（毕竟不是正解），但是我们还有一种神奇的线段树啊，常数接近树状数组的zkw线段树，关于不了解zkw线段树的同学可以先去百度，我们将利用这个线段树维护区间最小值，并做到区间更新，区间查询，每处理一个订单就将第s天到第t天的可租借教室减去d，直到出现一个最小值为负数，证明这个订单无法满足，实测，zkw线段树的效率甚至会快于二分答案，代码如下：
2018/10/20更新：下面的代码的区间查询函数为闭区间版本，不符合zkw原本的开区间写法，且代码较长，修改后的版本在文章末尾。更新后的开区间写法只是碰巧在出错几率不超过$\frac{1}{2^n}$的情况下查询到了全局最小值而已，碰巧A掉了所有的点，请大家不要模仿，好好的写闭区间吧。
//重写借教室 基于ZWK线段树
#include<bits/stdc++.h>
using namespace std;
int n,m,k;
int c[4000008*2];
int cnt;
int ls,rt,va;
void build(){
for(m=1;m<n+2;m<<=1);
for(int i=m+1;i<=m+n;i++){
cin >> c[i];
}
int temp=0;
for(int i=(m+n)/2;i;i--){
temp=min(c[i+i],c[i+i+1]);
c[i+i]-=temp;
c[i+i+1]-=temp;
c[i]+=temp;
}
}
void change(int s,int t,int value){
int temp=0;
for(s=s+m-1,t=t+m+1;s^t^1;s>>=1,t>>=1){
if(~s&1)c[s^1]+=value;
if(t&1)c[t^1]+=value;
temp=min(c[s],c[s^1]),c[s]-=temp,c[s^1]-=temp,c[s>>1]+=temp;
temp=min(c[t],c[t^1]),c[t]-=temp,c[t^1]-=temp,c[t>>1]+=temp;
}
for(;s>1;s>>=1){
temp=min(c[s],c[s^1]);c[s]-=temp;c[s^1]-=temp;c[s>>1]+=temp;
}
}
bool ask(int s,int t,int v=0){
if (s==t){
s=s+m;
int res=0;
while(s>1)res+=c[s>>=1];
return res>=0;
}
int lans=0;
int rans=0;
for(s=s+m,t=t+m;s^t^1;s>>=1,t>>=1){
lans+=c[s];
rans+=c[t];
if(~s&1)lans=min(lans,c[s^1]);
if(t&1)rans=min(rans,c[t^1]);
}
int res = min(lans,rans);
while(s>1)res+=c[s>>=1];
if (res<v) return false;
return true;
}
int main(){
ios::sync_with_stdio(false);
cin.tie(0);
cin >> n >> k;
build();
while(k--){
cnt++;
cin >> va >> ls >> rt;
change(ls,rt,-va);
if (ask(ls,rt)==false){
cout << "-1" << endl;
cout << cnt << endl;
return 0;
}
}
cout << "0" << endl;
return 0;
}测评结果如下:
2018/10/20更新：开区间写法，顺便在此指出《统计的力量》原PPT的一处错误，即区间查询开区间写法中的lans与rans的初值应赋为闭区间的左右端点，而非开区间的左右端点，请自行对比《统计的力量》标记永久化中的写法和如下ask函数的不同。不过zkw的开区间写法还是错的……这点倒是没错。反正是查询整体最小值，直接看根节点c[1]就好了嘛，ask函数都可以不用写了，少了20行代码呢。
//重写借教室 基于ZWK线段树
#include<bits/stdc++.h>
using namespace std;
int n,m,k;
int c[4000008*2];
int cnt;
int ls,rt,va;
void build(){
for(m=1;m<n+2;m<<=1);
for(int i=m+1;i<=m+n;i++)
cin >> c[i];
int temp=0;
for(int i=(m+n)/2;i;i--){
temp=min(c[i+i],c[i+i+1]);
c[i+i]-=temp;
c[i+i+1]-=temp;
c[i]+=temp;
}
}
void change(int s,int t,int value){
int temp=0;
for(s=s+m-1,t=t+m+1;s^t^1;s>>=1,t>>=1){
if(~s&1)c[s^1]+=value;
if(t&1)c[t^1]+=value;
temp=min(c[s],c[s^1]),c[s]-=temp,c[s^1]-=temp,c[s>>1]+=temp;
temp=min(c[t],c[t^1]),c[t]-=temp,c[t^1]-=temp,c[t>>1]+=temp;
}
for(;s>1;s>>=1)
temp=min(c[s],c[s^1]),c[s]-=temp,c[s^1]-=temp,c[s>>1]+=temp;
}
int main(){
ios::sync_with_stdio(false);
cin.tie(0);
cin >> n >> k;
int np=k;
build();
while(k--){
cnt++;
cin >> va >> ls >> rt;
change(ls,rt,-va);
if (c[1]<0){
cout << "-1" << endl;
cout << cnt << endl;
return 0;
}
}
cout << "0" << endl;
return 0;
}版权声明：本文为原创文章，版权归星夜的蓝天所有。
本文链接：http://poi.ac/archives/37/
本作品采用知识共享署名-非商业性使用 4.0 国际许可协议进行许可。转载时须注明出处及本声明
