# 51 条题解

• @ 2017-07-15 17:13:21

线段树碰线过。。

Accepted

#   状态  耗时  内存占用
#1  Accepted    3ms     4.34MiB
#2  Accepted    3ms     4.25MiB
#3  Accepted    4ms     4.25MiB
#4  Accepted    4ms     4.316MiB
#5  Accepted    5ms     4.25MiB
#6  Accepted    5ms     4.25MiB
#7  Accepted    30ms    8.625MiB
#8  Accepted    39ms    6.422MiB
#9  Accepted    50ms    6.297MiB
#10     Accepted    66ms    5.375MiB
#11     Accepted    63ms    10.977MiB
#12     Accepted    69ms    11.027MiB
#13     Accepted    106ms   7.293MiB
#14     Accepted    79ms    7.324MiB
#15     Accepted    386ms   22.543MiB
#16     Accepted    537ms   22.422MiB
#17     Accepted    693ms   22.418MiB
#18     Accepted    846ms   22.668MiB
#19     Accepted    1003ms  23.625MiB
#20     Accepted    1051ms  23.875MiB
代码

#include<cstdio>
#include<algorithm>
#include<cstring>
using namespace std;
const int MAX = 1000000 + 2;
using namespace std;
int tree[MAX * 8];
int data[MAX];
int lazy[MAX * 8];
int n, m, tot;
void check(int rt)
{
if(tree[rt] < 0)
{
printf("-1\n%d", tot);
exit(0);
}
}
void up(int rt)
{
tree[rt] = min(tree[rt << 1] , tree[rt << 1 | 1]);
check(rt);
}
void built(int l, int r, int rt)
{
if(l == r)
{
tree[rt] = data[l];
return;
}
int m = l + (r - l) / 2;
built(l, m, rt << 1);
built(m + 1, r, rt << 1 | 1);
up(rt);
}
void down(int rt, int L, int R)
{
if(lazy[rt])
{
int m = L + (R - L) / 2;

lazy[rt * 2] += lazy[rt];
lazy[rt * 2 + 1] += lazy[rt];
tree[rt * 2] -= lazy[rt];
tree[rt * 2 + 1] -= lazy[rt];
lazy[rt] = 0;
}
}
void modify(int L, int R, int l, int r, int val, int rt)
{

if(L >= l && R <= r)
{
tree[rt] -= val;
check(rt);
lazy[rt] += val;
return;
}
check(rt);
down(rt, L, R);
int m = L + (R - L) / 2;
if(m >= l) modify(L, m, l, r, val, rt * 2);
if(m < r) modify(m + 1, R, l, r, val, rt * 2 + 1);
up(rt);
}
void solve(int n, int m)
{
int a, b, c;
for(int i = 1; i <= m; i++)
{
tot = i;
scanf("%d %d %d", &c, &a, &b);
modify(1, n, a, b, c, 1);
}
printf("0");
return;
}
void init(int n, int m)
{

for(int i = 1; i <= n; i++)
scanf("%d", &data[i]);
built(1, n, 1);
}
int main()
{
//  freopen("in.txt","r", stdin);
scanf("%d %d", &n, &m);
init(n, m);
solve(n, m);
return 0;
}

• @ 2017-10-30 07:48:09

坑点：
1.修改前缀和时要在上一个状态进行修改，不能从头到尾加
2.需要在一开始特判全都能过，否则一TLE一WA
3.并不需要开long long
还有一些细碎的二分之类，自己注意

#include<iostream>
#include<cstring>
using namespace std;
int a[1000100],qian[1000010],gai[1000010];

struct cun{
int tou,wei,shu;
}q[1000010];

int main()
{
int n,i,left,right,mid,ci,m,last=1,haha=0,ans;
cin>>n>>m;
for(i=1;i<=n;i++)
{
cin>>a[i];
}
for(i=1;i<=m;i++)
cin>>q[i].shu>>q[i].tou>>q[i].wei;
left=0;
right=m;
for(i=1;i<=m;i++)
{
gai[q[i].tou]+=q[i].shu;
gai[q[i].wei+1]-=q[i].shu;
}
for(i=1;i<=n;i++)
{
qian[i]=qian[i-1]+gai[i];
if(qian[i]>a[i])
break;
}
if(i>n)
{
cout<<0;
return 0;
}
memset(qian,0,sizeof(qian));
memset(gai,0,sizeof(gai));
while(left<=right)
{
mid=(left+right)/2;
if(mid>haha)
{
for(i=haha+1;i<=mid;i++)
{
gai[q[i].tou]-=q[i].shu;
gai[q[i].wei+1]+=q[i].shu;
}
}
else
{
for(i=mid+1;i<=haha;i++)
{
gai[q[i].tou]+=q[i].shu;
gai[q[i].wei+1]-=q[i].shu;
}
}
haha=mid;
for(i=1;i<=n;i++)
{
qian[i]=qian[i-1]+gai[i];
if(qian[i]+a[i]<0)
break;
}
if(i>n)
{
left=mid+1;
}
else
{
ans=mid;
right=mid-1;
}
}
cout<<-1<<endl;
cout<<ans;

return 0;
}

• @ 2017-11-23 17:20:08

一道较为基础的线段树题目。
大体的思路是每输入一组数据，用find函数查看一下是否可行；
如果不行，就输出-1，还有当前的申请序号，return 0；
如果一直没有return 0，说明都可以，输出0，return 0；
对于find函数大体思路：
区间最值与给的教室数大小关系的判断，都可以就可以，任何一个不行就都不行；
当find发现可以借的时候才调用；
线段树对于区间最值的维护，对于符合的根节点tree[i]-=教室数；
并用lazy数组维护；
#include<iostream>
#include<algorithm>
#include<cstdio>
using namespace std;
int tree[24000010],a[600010],lazy[24000010],n,m,s,r,ans;
{
x=0;
char c=getchar();
while (c<'0'||c>'9') c=getchar();
while (c>='0'&&c<='9')
{
x=x*10+c-'0';
c=getchar();
}
}
void build(int x,int l,int r)
{
if (l==r)
{
tree[x]=a[l];
return;
}
int mid=(l+r)>>1;
build(x<<1,l,mid);
build(x<<1|1,mid+1,r);
tree[x]=min(tree[x<<1],tree[x<<1|1]);
}
void pushdown(int node,int l,int r)
{
tree[node<<1]+=lazy[node];
lazy[node<<1]+=lazy[node];
tree[node<<1|1]+=lazy[node];
lazy[node<<1|1]+=lazy[node];
lazy[node]=0;
}
void add(int node,int l,int r,int x,int y,int z)
{
if (l==x&&r==y)
{
tree[node]-=z;
lazy[node]-=z;
return;
}
if (lazy[node]) pushdown(node,l,r);
int mid=(l+r)>>1;
if (y<=mid)
else
if (mid<x)
else
{
}
tree[node]=min(tree[node<<1],tree[node<<1|1]);
}
bool find(int node,int l,int r,int x,int y,int z)
{
if(r==y&&x==l)
{
if (tree[node]>=z)
return true;
else
return false;
}
if (lazy[node]) pushdown(node,l,r);
int mid=(l+r)/2;
if (y<=mid)
return find(node<<1,l,mid,x,y,z);
else
if (x>mid)
return find(node<<1|1,mid+1,r,x,y,z);
else
return find(node<<1,l,mid,x,mid,z)&find(node<<1|1,mid+1,r,mid+1,y,z);
}
int main()
{
for(int i=1;i<=n;i++)
build(1,1,n);
for (int i=1;i<=m;i++)
{
int x,y,z;
if (find(1,1,n,x,y,z))
{
}
else
{
cout<<-1<<endl;
cout<<i<<endl;
return 0;
}
}
cout<<0<<endl;
}

• @ 2018-08-22 20:33:27

二分答案
知识准备：使用前缀数组处理数组区间标记，单点查询。
定义sum[i]=j ，假设我们要修改多个区间 [a,b]，区间中每个元素都+c；然后我们询问每一个点，问值为多少？（N<=100w）
如果真正去标记区间[a,b]的话，时间复杂度为 O(n^2) ，显然不行。
那么我们就用一种特殊的方法来处理：
sum[a] + = c; sum[ b + 1 ] - = c;
然后我们从前到后对sum数组累加，每累加一次sum[i]就会得到点i的值。
前缀数组标记的时间复杂度为O(1),单点查询的复杂度为O(n);
借教室的题意分析：从前到后找到第一个不符合要求的订单即可！
也就是check (1,ans-1)==1;
而check (1,ans)==0的那个点ans。显然符合二分的思想，二分的是订单的编号，难点就是如何维护前缀数组sum[ ] ?
我们引入now变量，初值为0，记录当前sum数组中已经记录了从1到now的所有的订单的数据。Int mid=(l+r)>>1;
if(now<mid) 说明要把[now+1,mid]的订单加入到sum数组。
else(now>=mid) 说明要把[mid+1,now]的订单从sum数组中删除。
然后更新now=mid。
本题还有一个难点就是如何确定二分答案的左右端点！
左端点很好得出，可以为0或者1
右端点就有说道了，因为有一种情况是所有的订单都满足和第m个订单不满足情况的区别。
所有我们引入一个多余的空订单，即右端点r=m+1.
庆幸的是输出“0”的测试点并不多——防骗分。

#include<cstdio>
#include<cstring>
#include<cmath>
#include<iostream>
#include<algorithm>
using namespace std;
int f,n;
int room[1000001],d[1000001],c[1000001];
int s[1000001],t[1000001],a[1000001];
bool check(int k)
{
if(k>f)
{
for(int i=f+1;i<=k;i++)
{
a[s[i]]-=d[i];
a[t[i]+1]+=d[i];
}
}
else
{
for(int i=k+1;i<=f;i++)
{
a[s[i]]+=d[i];
a[t[i]+1]-=d[i];
}
}
f=k;
for(int i=1;i<=n;i++)
{
c[i]=c[i-1]+a[i];
if(c[i]+room[i]<0)
return false;
}
return true;
}
int main()
{
int m,ans;
scanf("%d%d",&n,&m);
for(int i=1;i<=n;i++)
{
scanf("%d",&room[i]);
}
for(int i=1;i<=m;i++)
{
scanf("%d%d%d",&d[i],&s[i],&t[i]);
}
int l=1,r=m+1;
while(l<r)
{
int mid=(l+r)>>1;
if(check(mid))
l=mid+1;
else
r=mid;
}
if(check(m))
{
printf("0");
return 0;
}
printf("-1\n%d",l);
return 0;
}

• @ 2017-10-27 17:00:06

二分答案
跑的飞起

#include <cmath>
#include <cstdio>
#include <cstring>
#include <cstdlib>
#include <algorithm>
#include <cctype>
#include <vector>
#include <queue>
using namespace std;
int f,n;
int room[1000001],mon[1000001],c[1000001];
int s[1000001],t[1000001],a[1000001];
bool check(int k)
{
if(k>f)
{
for(int i=f+1;i<=k;i++)
{
a[s[i]]-=mon[i];
a[t[i]+1]+=mon[i];
}
}
else
{
for(int i=k+1;i<=f;i++)
{
a[s[i]]+=mon[i];
a[t[i]+1]-=mon[i];
}
}
f=k;
for(int i=1;i<=n;i++)
{
c[i]=c[i-1]+a[i];
if(c[i]+room[i]<0)
{
return false;
}
}
return true;
}
int main()
{
int m,l=0,r,mid,ans;
scanf("%d%d",&n,&m);
for(int i=1;i<=n;i++)
{
scanf("%d",&room[i]);
}
for(int i=1;i<=m;i++)
{
scanf("%d%d%d",&mon[i],&s[i],&t[i]);
}
r=m;
if(check(m)==true)
{
printf("0");
return 0;
}
while(l<=r)
{
mid=(l+r)/2;
if(check(mid)==true)
{
l=mid+1;
}
else
{
ans=mid;
r=mid-1;
}
}
printf("-1\n%d",ans);
return 0;
}

• @ 2017-08-11 21:21:57

二分答案。。。常数优化写不下去了就这样吧。。。交上去之后还挺快
依旧是循环展开+读入优化+寄存器变量，没啥新鲜的

#include <cstdio>
#include <cctype>

const int MAXN = 1000010;

int n, m, ans, a[MAXN], s[MAXN], t[MAXN], k[MAXN];

//读入优化
char _c; int sum(0);
while (!isdigit(_c = getchar()));
do sum = sum * 10 + _c - '0';
while (isdigit(_c = getchar()));
return sum;
}

//其实judge也是可以搞些小优化的但是我不想写了。。。
inline bool judge(int x) {
//memset(num, 0, sizeof(num));
int num[MAXN] = {0}; //我猜测这样可能比memset快一些
for (register int i = 1; i <= x; ++i)
num[s[i]] += k[i], num[t[i] + 1] -= k[i];
register int sa(0);
for (register int i = 1; i <= n; ++i) {
sa += num[i];
if (sa > a[i])
return false;
}
return true;
}

int main() {
//前方高能，密集恐惧症患者慎入【滑稽
for (register int i = 1; i < n; i += 2)
(n & 1) && (a[n] = ReadInt()); //这里就是if else好孩子不要学
for (register int i = 1; i < m; i += 2)
register int l = 1, r = m, mid = -1;
while (l <= r) {
mid = (l + r) >> 1;
(judge(mid)) ? (l = mid + 1, ans = mid) : (r = mid - 1);
}
//其实这里还可以写的更优美
(ans < m) ? printf("-1\n%d\n", ans + 1) : printf("0\n");
return 0;
}

qwq就是这样

#1 Accepted 8ms 10.0MiB
#2 Accepted 7ms 10.0MiB
#3 Accepted 10ms 10.07MiB
#4 Accepted 10ms 10.094MiB
#5 Accepted 8ms 10.07MiB
#6 Accepted 10ms 10.0MiB
#7 Accepted 39ms 10.488MiB
#8 Accepted 45ms 10.469MiB
#9 Accepted 44ms 12.418MiB
#10 Accepted 48ms 16.051MiB
#11 Accepted 46ms 12.496MiB
#12 Accepted 43ms 14.527MiB
#13 Accepted 44ms 12.508MiB
#14 Accepted 45ms 14.598MiB
#15 Accepted 289ms 19.301MiB
#16 Accepted 317ms 19.305MiB
#17 Accepted 349ms 19.539MiB
#18 Accepted 367ms 19.406MiB
#19 Accepted 395ms 19.301MiB
#20 Accepted 393ms 19.305MiB

比线段树要快

• @ 2017-08-11 21:23:08

其实我一开始也是想的线段树，但是我本地测的貌似有卡线段树的数据，需要优化

• @ 2017-10-25 11:32:21

全部加register啊！
为啥用咸鱼读优不写iobuff或者mmap?

• @ 2017-10-25 11:32:21

全部加register啊！
为啥用咸鱼读优不写iobuff或者mmap?

• @ 2017-10-27 21:34:58

@call_me_std: qwq好久之前写题全用register挂掉了。。。至于后两个我第一次听说qwq待我去学学

• @ 2017-10-27 21:35:09

@call_me_std: %%%谢谢dalao

• @ 2015-11-02 17:42:42

var a,ca,d,s,t:array[0..1000005] of longint;
i,j,k,l,n,m,r,o,now:longint;
tmt,ans:int64;
p:boolean;
begin
for i:=1 to n do read(a[i]);
for i:=1 to m do read(d[i],s[i],t[i]);
d[m+1]:=a[1]+1; s[m+1]:=1; t[m+1]:=1;
l:=1; r:=m+1; now:=0;
while l<=r do
begin
ans:=l+((r-l) shr 1);
if ans>now then
for i:=now+1 to ans do
begin
inc(ca[s[i]],d[i]);
dec(ca[t[i]+1],d[i]);
end
else
for i:=ans+1 to now do
begin
dec(ca[s[i]],d[i]);
inc(ca[t[i]+1],d[i]);
end;
now:=ans;
tmt:=0;
p:=true;
for i:=1 to n do
begin
tmt:=tmt+ca[i];
if tmt>a[i] then begin p:=false; break; end;
end;
if p then l:=ans+1
else r:=ans-1;
end;
if l=m+1 then writeln(0)
else
begin
writeln(-1);
writeln(l);
end;
end.
数组把int64改成longint，最慢的从900+ms变成了600+ms，洛谷上更是从超时两个点到最慢的600+ms，告诉我为什么。
思路：恩二分的话不用讲，然后就是判断满不满足的部分。
用到了一个记录的数组，这个数组的性质是：ca[i]表示a[i]这个数比a[i-1]大ca[i]，然后我想你已经知道了。
这个数组其实就是记录一个差值，然后使区间加减的复杂度变成了O（1），但是查询就是O（n）（查询一个和查询N个复杂度一样）。

• @ 2019-02-15 09:17:08

每个测试点不止1秒？

• @ 2018-02-11 11:09:07

差分+二分答案

#include<iostream>
#include<cstdio>
#include<cmath>
#include<cstdlib>
#include<algorithm>
#include<cstring>
using namespace std;
#define Maxn 1000001
long long n,m,s[Maxn],t[Maxn],le,ri,mid,ans,sum[Maxn];
long long r[Maxn],d[Maxn],minn=Maxn,e;
bool check(long long x)
{
memset(sum,0,sizeof(sum));
for(int i=1;i<=x;i++)
{
sum[s[i]]+=d[i];
sum[t[i]+1]-=d[i];
}
long long ss=0;
for(int i=1;i<=n;i++)
{
ss+=sum[i];
if(ss>r[i])
{
minn=min(minn,x);
return false;
}
}
return true;
}
int main()
{
ios::sync_with_stdio(false);
cin>>n>>m;
for(int i=1;i<=n;i++)
cin>>r[i];
for(int i=1;i<=m;i++)
cin>>d[i]>>s[i]>>t[i];
le=1;
ri=m;
while(le<ri)
{
mid=(le+ri)/2;
if(check(mid))
le=mid+1;
else
ri=mid;
}
if(minn==Maxn)
cout<<0;
else
cout<<-1<<endl,cout<<minn<<endl;
return 0;
}

就完事了

• @ 2017-10-24 23:01:24

Lazy线段树，1234ms居然没TLE

# 状态 耗时 内存占用

#1 Accepted 4ms 380.0 KiB
#2 Accepted 4ms 348.0 KiB
#3 Accepted 3ms 384.0 KiB
#4 Accepted 4ms 372.0 KiB
#5 Accepted 4ms 360.0 KiB
#6 Accepted 4ms 348.0 KiB
#7 Accepted 42ms 3.219 MiB
#8 Accepted 57ms 3.734 MiB
#9 Accepted 76ms 3.836 MiB
#10 Accepted 96ms 2.375 MiB
#11 Accepted 104ms 2.859 MiB
#12 Accepted 116ms 2.492 MiB
#13 Accepted 150ms 4.25 MiB
#14 Accepted 116ms 3.082 MiB
#15 Accepted 440ms 18.121 MiB
#16 Accepted 619ms 17.84 MiB
#17 Accepted 859ms 17.824 MiB
#18 Accepted 943ms 16.742 MiB
#19 Accepted 1185ms 18.117 MiB
#20 Accepted 1234ms 18.461 MiB

#include<cstdio>
#include<cstring>
#include<algorithm>
#include<cmath>
#include<iostream>
using namespace std;
template<class T> inline void read(T &_a){
bool f=0;int _ch=getchar();_a=0;
while(_ch<'0' || _ch>'9'){if(_ch=='-')f=1;_ch=getchar();}
while(_ch>='0' && _ch<='9'){_a=(_a<<1)+(_a<<3)+_ch-'0';_ch=getchar();}
if(f)_a=-_a;
}

const int maxn=1000001;
struct fff
{
int minn,lazy;
}node[(maxn<<2)+(maxn<<1)];
int n,m;

inline void pushup(int u)
{
node[u].minn=min(node[u<<1].minn,node[u<<1|1].minn);
}

inline void pushdown(int u)
{
if(node[u].lazy)
{
node[u<<1].lazy+=node[u].lazy;
node[u<<1|1].lazy+=node[u].lazy;
node[u<<1].minn-=node[u].lazy;
node[u<<1|1].minn-=node[u].lazy;
node[u].lazy=0;
}
}

void build(int u,int l,int r)
{
if(l==r) { read(node[u].minn); return ; }
int mid=(l+r)>>1;
build(u<<1,l,mid);
build(u<<1|1,mid+1,r);
pushup(u);
}

int query(int u,int l,int r,int L,int R)
{
if(L<=l&&r<=R) return node[u].minn;
pushdown(u);
int mid=(l+r)>>1;
if(R<=mid) return query(u<<1,l,mid,L,R);
if(L>mid) return query(u<<1|1,mid+1,r,L,R);
return min(query(u<<1,l,mid,L,R),query(u<<1|1,mid+1,r,L,R));
}

void update(int u,int l,int r,int L,int R,int val)
{
if(L<=l&&r<=R)
{
node[u].lazy+=val;
node[u].minn-=val;
return ;
}
pushdown(u);
int mid=(l+r)>>1;
if(L<=mid) update(u<<1,l,mid,L,R,val);
if(R>mid) update(u<<1|1,mid+1,r,L,R,val);
pushup(u);
return ;
}

int main()
{
build(1,1,n);
for (register int cas=1,d,s,j;cas<=m;++cas)
{
int num=query(1,1,n,s,j);
if(num<d) {printf("-1\n%d",cas); return 0;}
update(1,1,n,s,j,d);
}
printf("0");
return 0;
}

• @ 2017-10-17 20:10:38

二分：

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
#define For(aHJEfaks, fwbjkWK, AENGIBv) for (int aHJEfaks = fwbjkWK; aHJEfaks <= AENGIBv; ++aHJEfaks)
#define For2(aHJEfaks, fwbjkWK, AENGIBv) for (auto aHJEfaks = fwbjkWK; aHJEfaks != AENGIBv; ++aHJEfaks)
int n, m;
int ma[5000000];
int nu[5000000], be[5000000], ed[5000000];
int oka[5000000];
bool ok(int x){
For(i, 1, n){
oka[i] = 0;
}
For(i, 1, x){
oka[be[i]] += nu[i];
oka[ed[i] + 1] -= nu[i];
}
int t = 0;
For(i, 1, n){
t += oka[i];
if (t > ma[i]){
return false;
}
}
return true;
}
int bi(int l, int r){
if (l == r){
return l;
}
int t = (l + r) / 2;
if (ok(t)){
return bi(t + 1, r);
} else{
return bi(l, t);
}
}
int main(){
cin >> n >> m;
For(i, 1, n){
cin >> ma[i];
}
For(i, 1, m){
cin >> nu[i] >> be[i] >> ed[i];
}
if (ok(m)){
cout << 0 << endl;
return 0;
}
int ans = bi(1, m);

cout << -1 << endl << ans << endl;

return 0;
}
/*
*
5 2
100 10001 100 1000 1000
1 2 3
1 1 2
*/

线段树：

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
#define For(aHJEfaks, fwbjkWK, AENGIBv) for (int aHJEfaks = fwbjkWK; aHJEfaks <= AENGIBv; ++aHJEfaks)
#define For2(aHJEfaks, fwbjkWK, AENGIBv) for (auto aHJEfaks = fwbjkWK; aHJEfaks != AENGIBv; ++aHJEfaks)
int l[10000000], r[10000000], ma[10000000], mi[10000000], sp[10000000];
int n, m;

void in(int le, int ri, int k){
l[k] = le;
r[k] = ri;
if (le == ri){
mi[k] = ma[le];
return;
}
int mid = (le + ri) / 2;
in(le, mid, 2 * k);
in(mid + 1, ri, 2 * k + 1);
mi[k] = min(mi[2 * k], mi[2 * k + 1]);
}
int smi(int gl, int gr, int k){
if (gl == l[k] && gr == r[k]){
return (mi[k] + sp[k]);
}
int pm = (l[k] + r[k]) / 2;
if (gr <= pm){
return (smi(gl, gr, 2 * k) + sp[k]);
}
if (gl >= pm + 1){
return (smi(gl, gr, 2 * k + 1) + sp[k]);
}
return (min(smi(gl, pm, 2 * k), smi(pm + 1, gr, 2 * k + 1)) + sp[k]);
}

void oc(int gl, int gr, int gn, int k){
if (gl == l[k] && gr == r[k]){
sp[k] -= gn;
return;
}
int pm = (l[k] + r[k]) / 2;
if (gr <= pm){
oc(gl, gr, gn, 2 * k);
mi[k] = min(mi[2 * k] + sp[2 * k], mi[2 * k + 1] + sp[2 * k + 1]);
return;
}
if (gl >= pm + 1){
oc(gl, gr, gn, 2 * k + 1);
//        mi[k] = min(smi(gl, pm, 2 * k), smi(pm + 1, gr, 2 * k + 1));
mi[k] = min(mi[2 * k] + sp[2 * k], mi[2 * k + 1] + sp[2 * k + 1]);
return;
}
oc(gl, pm, gn, 2 * k);
oc(pm + 1, gr, gn, 2 * k + 1);
//    mi[k] = min(smi(gl, pm, 2 * k), smi(pm + 1, gr, 2 * k + 1));
mi[k] = min(mi[2 * k] + sp[2 * k], mi[2 * k + 1] + sp[2 * k + 1]);
}
int main(){
cin >> n >> m;
For(i, 1, n){
scanf("%d", &ma[i]);
}
in(1, n, 1);
For(tosn, 1, m){
int num, be, en;
cin >> num >> be >> en;
//        cout << smi(be, en, 1) << ' ';
//        cout << smi(be, en, 1) << endl;
if (smi(be, en, 1) < num){
cout << -1 << endl << tosn << endl;
return 0;
}
oc(be, en, num, 1);
//        For(i, 1, n){
//            cout << smi(i, i, 1) << ' ';
//        }
//
//        cout << endl;
}
cout << 0 << endl;
return 0;
}

• @ 2017-08-13 16:35:37

2分

#include <cmath>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <iomanip>
#include <algorithm>
#include <vector>
#include <deque>
#include <limits>
#include <string>
#include <sstream>
using namespace std;

const int oo_min=0xcfcfcfcf,oo_max=0x3f3f3f3f;

int n,m;
int a[1048576+1];
int s[1048576+1];
int t[1048576+1];
int num[1048576+1];
int sum[1048576+1];

int check_1(int x)
{
memset(sum,0,sizeof(sum));
for (int i=1;i<=x;i++)
sum[s[i]]+=num[i],sum[t[i]+1]-=num[i];
int ans=0;
for (int i=1;i<=n;i++)
{
ans+=sum[i];
if (ans>a[i])
return 0;
}
return 1;
}

int main()
{
while (~scanf("%d%d",&n,&m))
{
for (int i=1;i<=n;i++)
scanf("%d",&a[i]);
for (int i=1;i<=m;i++)
scanf("%d%d%d",&num[i],&s[i],&t[i]);
int left,right;
for (left=1,right=m;right-left>1;)
{
int mid=(left+right)/2;
if (check_1(mid))
left=mid;
else
right=mid;
}
int ans=oo_max;
if (check_1(left)==0)
ans=left;
else if (check_1(right)==0)
ans=right;
if (ans<oo_max)
{
printf("%d\n",-1);
printf("%d\n",ans);
}
else
printf("%d\n",0);
}
}

Segment Tree

#include <cmath>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <iomanip>
#include <algorithm>
#include <vector>
#include <deque>
#include <limits>
#include <string>
#include <sstream>
using namespace std;

const int oo_min=0xcfcfcfcf,oo_max=0x3f3f3f3f;

struct segment_tree_1
{
int l,r,mid,x,lazy;
}st[2*1048576+2];

int n,m;
int a[1048576+1];

void build_segment_tree_1(int now,int l,int r)
{
st[now].l=l,st[now].r=r,st[now].mid=(l+r)/2,st[now].lazy=0;
if (l<r)
{
if (l<=st[now].mid)
build_segment_tree_1(now*2,l,st[now].mid);
if (st[now].mid+1<=r)
build_segment_tree_1(now*2+1,st[now].mid+1,r);
}
if (l==r)
st[now].x=a[l];
else
st[now].x=min(st[now*2].x,st[now*2+1].x);
}

void push_down_1(int now)
{
if (st[now].lazy)
{
st[now*2].lazy+=st[now].lazy,st[now*2+1].lazy+=st[now].lazy;
st[now*2].x-=st[now].lazy,st[now*2+1].x-=st[now].lazy;
st[now].lazy=0;
}
}

void update_1(int now,int l,int r,int x)
{
if (st[now].l==l&&st[now].r==r)
{
st[now].x-=x;
st[now].lazy+=x;
return;
}
else
{
push_down_1(now);
if (r<=st[now].mid)
update_1(now*2,l,r,x);
else if (st[now].mid+1<=l)
update_1(now*2+1,l,r,x);
else
update_1(now*2,l,st[now].mid,x),update_1(now*2+1,st[now].mid+1,r,x);
st[now].x=min(st[now*2].x,st[now*2+1].x);
}
}

int sum_1(int now,int l,int r)
{
if (st[now].l==l&&st[now].r==r)
return st[now].x;
else
{
push_down_1(now);
if (r<=st[now].mid)
return sum_1(now*2,l,r);
else if (st[now].mid+1<=l)
return sum_1(now*2+1,l,r);
else
return min(sum_1(now*2,l,st[now].mid),sum_1(now*2+1,st[now].mid+1,r));
}
}

int main()
{
while (~scanf("%d%d",&n,&m))
{
int flag=0;
for (int i=1;i<=n;i++)
scanf("%d",&a[i]);
build_segment_tree_1(1,1,n);
for (int i=1;i<=m;i++)
{
int l,r,x;
scanf("%d%d%d",&x,&l,&r);
if (flag==0)
{
if (sum_1(1,l,r)>=x)
update_1(1,l,r,x);
else
{
printf("%d\n",(flag=-1));
printf("%d\n",i);
}
}
}
if (flag==0)
printf("%d\n",flag);
}
}

• @ 2017-08-13 16:36:16

很H2O的题

• @ 2017-08-05 15:56:03

2012NOIP DAY2T1
方法1：线段树
使用线段树来维护一个区间的最小值，每次对于输入的L,R区间进行区间修改，如果最小值<0，则无法成功借教室（加了一大堆玄学优化，终于勉强没T）

#include <cstdio>
#include <stdlib.h>
using namespace std;
const int maxn=1e6+100;
struct tree{
int minn;
int l,r;
}st[maxn*4];
int a[maxn];
int w;
inline int min(int a,int b)
{
return a < b ? a : b;
}
void build(int o,int l,int r)
{
st[o].l=l,st[o].r=r;
if(l==r)
{
st[o].minn=a[l];
return;
}
int mid=(r+l)>>1;

build((o<<1),l,mid);
build((o<<1)|1,mid+1,r);

st[o].minn=min(st[(o<<1)].minn,st[(o<<1)|1].minn);
}
inline void push_down(int o)
{

}
inline void query(int o,int ql,int qr,int ad)
{
int l=st[o].l,r=st[o].r;

if(l==ql&&r==qr)
{
if(st[o].minn<0)
{
printf("-1\n%d\n",w);
exit(0);
}
return;
}

int mid=(l+r)>>1;

st[o].minn=min(st[(o<<1)].minn,st[(o<<1)|1].minn);
}
{
int data=0,w=1; char ch=0;
while(ch!='-' && (ch<'0' || ch>'9')) ch=getchar();
if(ch=='-') w=-1,ch=getchar();
while(ch>='0' && ch<='9') data=data*10+ch-'0',ch=getchar();
return data*w;
}
int main()
{
int n,m;

for (int i = 1; i <= n; i++)
{
char c = getchar();
while(c < '0' || c > '9')
c = getchar();
while(c >= '0' && c <= '9')
{
a[i] *= 10;
a[i] += c - '0';
c = getchar();
}
}

build(1,1,n);

for(int i=1;i<=m;i++)
{
int x,y,t;
w=i;
query(1,x,y,-t);
}

printf("0");

return 0;
}

方法2：二分+差分
二分能够成功的方案数，用差分进行区修改，暴力判断有没有超出限制的，时间复杂度O（nlogn）
其实跟线段树的复杂度相同，只是常数比较小，在数据爆炸的题里会快不少！

#include <cstdio>
#include <stdlib.h>
#include <iostream>
#include <cstring>
using namespace std;
const int maxn=1001000;
struct tree{
int l,r,t;
}a[maxn];
int d[maxn];
int b[maxn];
{
int data=0,w=1; char ch=0;
while(ch!='-' && (ch<'0' || ch>'9')) ch=getchar();
if(ch=='-') w=-1,ch=getchar();
while(ch>='0' && ch<='9') data=data*10+ch-'0',ch=getchar();
return data*w;
}
int n,m;
inline bool check(int mid)
{
memset(b,0,sizeof(b));

for(int i=1;i<=mid;i++)
b[a[i].l]+=a[i].t,b[a[i].r+1]-=a[i].t;

int s=0;

for(int i=1;i<=n;i++)
{
s+=b[i];
if(s>d[i])
return 0;
}

return 1;
}
int main()
{

for(int i=1;i<=n;i++)

for(int i=1;i<=m;i++)

int l=1;
int r=m;
int ans=0;
while(l<=r)
{
int mid=(l+r)/2;
if(!check(mid))
ans=mid,r=mid-1;
else
l=mid+1;
}

if(!ans)
printf("0");
else
printf("-1\n%d",ans);

return 0;
}

• @ 2017-07-17 11:30:57

一击！！！

#include<iostream>
#include<cstdio>
#define INF (0x3f3f3f3f)
using namespace std;
struct DA {int d,s,t;} da[1000010];
struct SGT {int l,r,mi,lz;} sgt[1000010<<2];
int n,m;
int spt[1000010];
int rint () {int num=0,f=1;char cc=getchar();while(cc<'0'||cc>'9') {if (cc=='-') f=-1;cc=getchar();}while(cc>='0'&&cc<='9') {num=num*10+cc-'0';cc=getchar();}return num*f;}
void sgtps (int id) {sgt[id].mi=min(sgt[id<<1].mi,sgt[id<<1|1].mi);return;}
void sgtdn (int id) {

sgt[id<<1].lz+=sgt[id].lz,sgt[id<<1].mi+=sgt[id].lz;
sgt[id<<1|1].lz+=sgt[id].lz,sgt[id<<1|1].mi+=sgt[id].lz;
sgt[id].lz=0;

}
void sgtbd (int l,int r,int id) {

sgt[id].l=l,sgt[id].r=r,sgt[id].lz=0;
if (l==r) {sgt[id].mi=spt[l];return;}
sgtbd(l,(l+r)>>1,id<<1),sgtbd(((l+r)>>1)+1,r,id<<1|1);
sgtps(id);

}
void sgtad (int l,int r,int val,int id) {

if (sgt[id].r<l||sgt[id].l>r) return;
if (sgt[id].l==l&&sgt[id].r==r) {sgt[id].lz+=val,sgt[id].mi+=val;return;}
sgtdn(id);
sgtps(id);

}
int sgtmi (int l,int r,int id) {

if (sgt[id].r<l||sgt[id].l>r) return INF;
if (sgt[id].l==l&&sgt[id].r==r) return sgt[id].mi;
sgtdn(id);
if (r<((sgt[id].l+sgt[id].r)>>1)) return sgtmi(l,r,id<<1);
else if (l>((sgt[id].l+sgt[id].r)>>1)) return sgtmi(l,r,id<<1|1);
else return min(sgtmi(l,(sgt[id].l+sgt[id].r)>>1,id<<1),sgtmi(((sgt[id].l+sgt[id].r)>>1)+1,r,id<<1|1));
sgtps(id);

}
int main () {

ios::sync_with_stdio(false);
n=rint(),m=rint();
for(int i=1;i<=n;i++) spt[i]=rint();
sgtbd(1,n,1);
int flag=0;
int cant;
for(int i=1;i<=m;i++) {
da[i].d=rint(),da[i].s=rint(),da[i].t=rint();
if (sgtmi(da[i].s,da[i].t,1)<0) {flag=i;break;}
}
if (!flag) cout<<"0"<<endl;
else cout<<"-1"<<endl<<flag<<endl;
return 0;

}

• @ 2016-05-03 19:47:21

两件事情：
1.被卡时限的首先优化读入。
2.结构体、类封装、位运算加速在这道题里面对于程序运行时间影响很小。

编译成功

测试数据 #0: Accepted, time = 46 ms, mem = 47528 KiB, score = 5
测试数据 #1: Accepted, time = 46 ms, mem = 47524 KiB, score = 5
测试数据 #2: Accepted, time = 31 ms, mem = 47524 KiB, score = 5
测试数据 #3: Accepted, time = 31 ms, mem = 47528 KiB, score = 5
测试数据 #4: Accepted, time = 31 ms, mem = 47524 KiB, score = 5
测试数据 #5: Accepted, time = 46 ms, mem = 47524 KiB, score = 5
测试数据 #6: Accepted, time = 93 ms, mem = 47528 KiB, score = 5
测试数据 #7: Accepted, time = 46 ms, mem = 47528 KiB, score = 5
测试数据 #8: Accepted, time = 62 ms, mem = 47528 KiB, score = 5
测试数据 #9: Accepted, time = 93 ms, mem = 47528 KiB, score = 5
测试数据 #10: Accepted, time = 93 ms, mem = 47524 KiB, score = 5
测试数据 #11: Accepted, time = 125 ms, mem = 47524 KiB, score = 5
测试数据 #12: Accepted, time = 125 ms, mem = 47524 KiB, score = 5
测试数据 #13: Accepted, time = 78 ms, mem = 47524 KiB, score = 5
测试数据 #14: Accepted, time = 437 ms, mem = 47528 KiB, score = 5
测试数据 #15: Accepted, time = 609 ms, mem = 47524 KiB, score = 5
测试数据 #16: Accepted, time = 734 ms, mem = 47524 KiB, score = 5
测试数据 #17: Accepted, time = 875 ms, mem = 47528 KiB, score = 5
测试数据 #18: Accepted, time = 1000 ms, mem = 47524 KiB, score = 5
测试数据 #19: Accepted, time = 1171 ms, mem = 47528 KiB, score = 5

#include<bits/stdc++.h>
using namespace std;
struct INTERVAL_DATA{
int left,right,Max,lazy;
INTERVAL_DATA(){
left=right=0;
lazy=0;
Max=0;
}
};
INTERVAL_DATA tree[3000000];
{
int x=0;
char ch=getchar();
while (ch<'0'||ch>'9') ch=getchar();
x=0;
while (ch<='9' && ch>='0')
{
x*=10,x+=ch-'0';
ch=getchar();
}
return x;
}
struct INTERVAL_TREE{
int nn;
INTERVAL_TREE(int height){
nn=height;

int h=0;
tree[0].left=0;tree[0].right=(1<<nn)-1;
for (int i=0;i<((1<<nn)-1);i++){
if (i>(2<<h)-2) h++;
tree[(i<<1)+1].left=tree[i].left;
tree[(i<<1)+2].left=(1<<(nn-h-1))|tree[i].left;
tree[(i<<1)+1].right=tree[(i<<1)+1].left+(1<<(nn-h-1))-1;
tree[(i<<1)+2].right=tree[(i<<1)+2].left+(1<<(nn-h-1))-1;
}
for (int i=0;i<(2<<nn)-1;i++){
tree[i].left++;
tree[i].right++;
}
}
void add(int root,int l,int r,int x){
if (l==tree[root].left&&r==tree[root].right) tree[root].lazy+=x;
else {
int mid=(tree[root].left+tree[root].right)>>1;
tree[(root<<1)+1].lazy+=tree[root].lazy;
tree[(root<<1)+2].lazy+=tree[root].lazy;
tree[root].lazy=0;

else {
}

tree[root].Max=max(tree[(root<<1)+1].lazy+tree[(root<<1)+1].Max,tree[(root<<1)+2].lazy+tree[(root<<1)+2].Max);
}
}
} a(20);
int main(){
int n,m,x,y,z;
for (int i=0;i<n;i++){
}

for (int i=0;i<m;i++){
if (tree[0].Max>0) {
cout<<"-1"<<endl<<i+1<<endl;
return 0;
}
}

cout<<0<<endl;
return 0;
}

• @ 2015-12-15 13:06:52

# 论**普通线段树**如何通过

编译成功

测试数据 #0: Accepted, time = 15 ms, mem = 48736 KiB, score = 5
测试数据 #1: Accepted, time = 15 ms, mem = 48740 KiB, score = 5
测试数据 #2: Accepted, time = 31 ms, mem = 48740 KiB, score = 5
测试数据 #3: Accepted, time = 15 ms, mem = 48732 KiB, score = 5
测试数据 #4: Accepted, time = 31 ms, mem = 48736 KiB, score = 5
测试数据 #5: Accepted, time = 15 ms, mem = 48736 KiB, score = 5
测试数据 #6: Accepted, time = 140 ms, mem = 48736 KiB, score = 5
测试数据 #7: Accepted, time = 140 ms, mem = 48740 KiB, score = 5
测试数据 #8: Accepted, time = 125 ms, mem = 48732 KiB, score = 5
测试数据 #9: Accepted, time = 140 ms, mem = 48732 KiB, score = 5
测试数据 #10: Accepted, time = 93 ms, mem = 48736 KiB, score = 5
测试数据 #11: Accepted, time = 101 ms, mem = 48732 KiB, score = 5
测试数据 #12: Accepted, time = 93 ms, mem = 48740 KiB, score = 5
测试数据 #13: Accepted, time = 101 ms, mem = 48732 KiB, score = 5
测试数据 #14: Accepted, time = 1671 ms, mem = 48740 KiB, score = 5
测试数据 #15: Accepted, time = 1296 ms, mem = 48736 KiB, score = 5
测试数据 #16: Accepted, time = 1250 ms, mem = 48736 KiB, score = 5
测试数据 #17: Accepted, time = 1125 ms, mem = 48732 KiB, score = 5
测试数据 #18: Accepted, time = 875 ms, mem = 48732 KiB, score = 5
测试数据 #19: Accepted, time = 843 ms, mem = 48736 KiB, score = 5
Accepted, time = 8115 ms, mem = 48740 KiB, score = 100

关键在于各种**奇技淫巧的优化**，我列出一些：
1. 正确的模拟方法 +30%
2. 堆式存储 +15%
3. 将所有除以2的运算变为位运算 +3%
4. 手动优化尾递归，vijos没有开优化 +5%
5. 循环使用迭代器写法 +5%
6. 读入优化 +3%
7. 大胆的使用int +2%
8. 使用结构体的默认构造函数 +1%
9. 线段树的插入和查询操作中对每条语句的必要性进行严格检查。删去没必要的语句 +2%

优化真是一件有趣的事......
实在过不了的可以到codevs上试试，codevs的机子好多了......

代码：
```c++
// 借教室

#include <cstdlib>
#include <string>
#include <cstdio>
#include <algorithm>

using namespace std;

#define NMAX 1000000
#define MMAX 1000000
#define MEMORY_SIZE 2097151

#define LEFT(x) (x << 1)
#define RIGHT(x) ((x << 1) | 1)
#define PARENT(x) (x >> 1)

// #define FMT "%lld"
// typedef long long ntype;
#define FMT "%d"
typedef int ntype;

struct Reservation {
Reservation() : start(0), end(0), need(0) {}
Reservation(ntype s, ntype t, ntype d) : start(s), end(t), need(d) {}

ntype start;
ntype end;
ntype need;
}; // struct Reservation

struct Node {
Node() : pos(1), l(0), r(0), sum(0) {}
Node(ntype _l, ntype _r) : pos(1), l(_l), r(_r), sum(0) {}

ntype pos;
ntype l;
ntype r;
ntype sum;
};

static ntype n, m;
static ntype r[NMAX + 10];
static Reservation q[MMAX + 10];
static Node heap[MEMORY_SIZE];
static bool flag;
static ntype id;

Node *build_tree(ntype lb, ntype rb, ntype p = 1);
void insert(ntype s, ntype t, ntype value, ntype p = 1);
ntype query(ntype d, ntype p = 1);

ntype x = 0;
char c = getchar();
while (c < '0' or c > '9') c = getchar();
while ('0' <= c and c <= '9') x = x * 10 + c - '0', c = getchar();
return x;
}

void initialize();
void quit();

int main() {
initialize();

for (Reservation *beg = &q[1]; beg != &q[n + 1]; beg++) {
insert(beg->start, beg->end, -beg->need, 1);
} // for

Reservation *j = &q[m + 1];
for (ntype i = 1; i <= n; i++) {
while (query(i, 1) < 0) {
j--;
insert(j->start, j->end, j->need, 1);
} // while
} // for

if (j != &q[m + 1]) {
flag = true;
id = j - &q[1] + 1;
}

quit();
return 0;
} // function main

void initialize() {

for (int *beg = &r[1]; beg != &r[n + 1]; beg++) *beg = read();
for (Reservation *beg = &q[1]; beg != &q[m + 1]; beg++)

flag = false;
id = 0;

build_tree(1, n);
}

void quit() {
if (!flag)
puts("0");
else {
puts("-1");
printf(FMT, id);
}
}

Node *build_tree(ntype lb, ntype rb, ntype p) {
Node *x = &heap[p];
x->l = lb;
x->r = rb;

if (lb != rb) {
ntype mid = (lb + rb) >> 1;
build_tree(lb, mid, LEFT(p));
build_tree(mid + 1, rb, RIGHT(p));
} else
x->sum = r[lb];

return x;
}

void insert(ntype s, ntype t, ntype value, ntype p) {
recursive:
Node *x = &heap[p];

if (s <= x->l and x->r <= t)
x->sum += value;
else {
ntype mid = (x->l + x->r) >> 1;

if (t <= mid) {
// insert(s, t, value, LEFT(p));
p = LEFT(p);
goto recursive;
} else if (s > mid) {
// insert(s, t, value, RIGHT(p));
p = RIGHT(p);
goto recursive;
} else {
insert(s, t, value, LEFT(p));
insert(s, t, value, RIGHT(p));
}
}
}

ntype query(ntype d, ntype p) {
ntype result = 0;

recursive:
Node *x = &heap[p];

if (d == x->l and d == x->r) return result + x->sum;

result += x->sum;
ntype mid = (x->l + x->r) >> 1;

if (d <= mid)
p = LEFT(p);
else
p = RIGHT(p);

goto recursive;
}

• @ 2015-11-22 16:00:53

你们也交交看，一样的程序有时AC有时TLE

评测结果
编译成功

测试数据 #0: Accepted, time = 0 ms, mem = 317268 KiB, score = 5
测试数据 #1: Accepted, time = 0 ms, mem = 317268 KiB, score = 5
测试数据 #2: Accepted, time = 15 ms, mem = 317272 KiB, score = 5
测试数据 #3: Accepted, time = 0 ms, mem = 317272 KiB, score = 5
测试数据 #4: Accepted, time = 0 ms, mem = 317268 KiB, score = 5
测试数据 #5: Accepted, time = 0 ms, mem = 317272 KiB, score = 5
测试数据 #6: Accepted, time = 31 ms, mem = 317268 KiB, score = 5
测试数据 #7: Accepted, time = 31 ms, mem = 317268 KiB, score = 5
测试数据 #8: Accepted, time = 46 ms, mem = 317272 KiB, score = 5
测试数据 #9: Accepted, time = 78 ms, mem = 317272 KiB, score = 5
测试数据 #10: Accepted, time = 78 ms, mem = 317268 KiB, score = 5
测试数据 #11: Accepted, time = 93 ms, mem = 317272 KiB, score = 5
测试数据 #12: Accepted, time = 140 ms, mem = 317272 KiB, score = 5
测试数据 #13: Accepted, time = 78 ms, mem = 317268 KiB, score = 5
测试数据 #14: Accepted, time = 437 ms, mem = 317272 KiB, score = 5
测试数据 #15: Accepted, time = 703 ms, mem = 317272 KiB, score = 5
测试数据 #16: Accepted, time = 937 ms, mem = 317272 KiB, score = 5
测试数据 #17: Accepted, time = 1218 ms, mem = 317272 KiB, score = 5
测试数据 #18: Accepted, time = 1500 ms, mem = 317272 KiB, score = 5
测试数据 #19: Accepted, time = 1625 ms, mem = 317272 KiB, score = 5
Accepted, time = 7010 ms, mem = 317272 KiB, score = 100
代码
#include <cstring>
#include <cstdio>
#include <algorithm>
using namespace std;
int n,m,a[1000003],p,tot;
int d,s,t;
struct arr{
int w,c;
}tr[1000003*40];

int f=1,x=0;
char s=getchar();
while(s<'0'||s>'9') s=getchar();
while(s>='0' && s<='9'){
x=x*10+(s-48);
s=getchar();
}
return f*x;
}

void push(int num){
tr[2*num].c+=tr[num].c;
tr[2*num+1].c+=tr[num].c;
tr[num].w-=tr[num].c;
tr[num].c=0;
}

void build(int num,int l,int r){
if (l==r){
tr[num].w=a[l];
return;
}
build(2*num,l,(l+r)/2);
build(2*num+1,(l+r)/2+1,r);
tr[num].w=min(tr[2*num].w,tr[2*num+1].w);
}

int find(int num,int l,int r){
if (tr[num].c) push(num);
if (l>t || r<s || l>r) return 2147483647;
if (s<=l && r<=t) return tr[num].w;
return min(find(2*num,l,(l+r)/2),find(2*num+1,(l+r)/2+1,r));
}

void insert(int num,int l,int r){
if (tr[num].c) push(num);
if (l>t || r<s || l>r) return;
if (s<=l && r<=t){
tr[num].w-=d;
tr[2*num].c+=d;
tr[2*num+1].c+=d;
return;
}
insert(2*num,l,(l+r)/2);
insert(2*num+1,(l+r)/2+1,r);
tr[num].w=min(tr[2*num].w,tr[2*num+1].w);
}

int main(){
build(1,1,n);
for (int i=1;i<=m;i++){
if (tot) continue;
int dd=find(1,1,n);
if (dd<d) p=i,tot++;
else insert(1,1,n);
}
if (tot) printf("-1\n%d\n",p);
else printf("0\n");
return 0;
}

评测结果
编译成功

测试数据 #0: Accepted, time = 0 ms, mem = 317272 KiB, score = 5
测试数据 #1: Accepted, time = 0 ms, mem = 317276 KiB, score = 5
测试数据 #2: Accepted, time = 0 ms, mem = 317272 KiB, score = 5
测试数据 #3: Accepted, time = 0 ms, mem = 317276 KiB, score = 5
测试数据 #4: Accepted, time = 15 ms, mem = 317276 KiB, score = 5
测试数据 #5: Accepted, time = 0 ms, mem = 317272 KiB, score = 5
测试数据 #6: Accepted, time = 31 ms, mem = 317276 KiB, score = 5
测试数据 #7: Accepted, time = 62 ms, mem = 317272 KiB, score = 5
测试数据 #8: Accepted, time = 78 ms, mem = 317272 KiB, score = 5
测试数据 #9: Accepted, time = 124 ms, mem = 317276 KiB, score = 5
测试数据 #10: Accepted, time = 124 ms, mem = 317272 KiB, score = 5
测试数据 #11: Accepted, time = 156 ms, mem = 317272 KiB, score = 5
测试数据 #12: Accepted, time = 187 ms, mem = 317276 KiB, score = 5
测试数据 #13: Accepted, time = 140 ms, mem = 317276 KiB, score = 5
测试数据 #14: Accepted, time = 873 ms, mem = 317272 KiB, score = 5
测试数据 #15: Accepted, time = 1341 ms, mem = 317272 KiB, score = 5
测试数据 #16: Accepted, time = 1700 ms, mem = 317276 KiB, score = 5
测试数据 #17: TimeLimitExceeded, time = 2012 ms, mem = 317276 KiB, score = 0
测试数据 #18: TimeLimitExceeded, time = 2012 ms, mem = 317276 KiB, score = 0
测试数据 #19: TimeLimitExceeded, time = 2012 ms, mem = 317276 KiB, score = 0
TimeLimitExceeded, time = 10867 ms, mem = 317276 KiB, score = 85
代码
#include <cstring>
#include <cstdio>
#include <algorithm>
using namespace std;
int n,m,a[1000003],p,tot;
int d,s,t;
struct arr{
int w,c;
}tr[1000003*40];

int f=1,x=0;
char s=getchar();
while(s<'0'||s>'9') s=getchar();
while(s>='0' && s<='9'){
x=x*10+(s-48);
s=getchar();
}
return f*x;
}

void push(int num){
tr[2*num].c+=tr[num].c;
tr[2*num+1].c+=tr[num].c;
tr[num].w-=tr[num].c;
tr[num].c=0;
}

void build(int num,int l,int r){
if (l==r){
tr[num].w=a[l];
return;
}
build(2*num,l,(l+r)/2);
build(2*num+1,(l+r)/2+1,r);
tr[num].w=min(tr[2*num].w,tr[2*num+1].w);
}

int find(int num,int l,int r){
if (tr[num].c) push(num);
if (l>t || r<s || l>r) return 2147483647;
if (s<=l && r<=t) return tr[num].w;
return min(find(2*num,l,(l+r)/2),find(2*num+1,(l+r)/2+1,r));
}

void insert(int num,int l,int r){
if (tr[num].c) push(num);
if (l>t || r<s || l>r) return;
if (s<=l && r<=t){
tr[num].w-=d;
tr[2*num].c+=d;
tr[2*num+1].c+=d;
return;
}
insert(2*num,l,(l+r)/2);
insert(2*num+1,(l+r)/2+1,r);
tr[num].w=min(tr[2*num].w,tr[2*num+1].w);
}

int main(){
build(1,1,n);
for (int i=1;i<=m;i++){
if (tot) continue;
int dd=find(1,1,n);
if (dd<d) p=i,tot++;
else insert(1,1,n);
}
if (tot) printf("-1\n%d\n",p);
else printf("0\n");
return 0;
}

• @ 2015-10-22 15:41:44

线段树 ！！经典模板
http://www.ofsxb.com/archives/455

• @ 2015-10-07 21:53:14

#include <cstdio>
#include <algorithm>
#include <cmath>
#include <cstring>
#include <iostream>
#include <queue>
#include <vector>
using namespace std;
#define N 1000010
struct Node{
int flag;
int Min;
}t[N*4];
int n,m;
int A[N];
bool pd=true;
{
int x=0,f=1;char ch=getchar();
while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();}
while(ch<='9'&&ch>='0'){x=x*10+ch-'0';ch=getchar();}
return x*f;
}
void Pushup(int i)
{
t[i].Min=min(t[i*2].Min,t[i*2+1].Min);
}
void BuildTree(int i,int l,int r)
{
if(l==r)
{
t[i].Min=A[l];
return;
}
int mid=(l+r)/2;
BuildTree(i*2,l,mid);
BuildTree(i*2+1,mid+1,r);
Pushup(i);
}
void Pushdown(int i)
{
if(t[i].flag==0)
return;
t[i*2].Min+=t[i].flag;
t[i*2+1].Min+=t[i].flag;
t[i*2].flag+=t[i].flag;
t[i*2+1].flag+=t[i].flag;
t[i].flag=0;
return;
}
void Updata(int i,int l,int r,int left,int right,int c)
{
if(l>=left&&r<=right)
{
t[i].Min-=c;
t[i].flag-=c;
if(t[i].Min<0)
pd=false;
return;
}
Pushdown(i);
int mid=(l+r)/2;
if(right<=mid)
Updata(i*2,l,mid,left,right,c);
else if(left>mid)
Updata(i*2+1,mid+1,r,left,right,c);
else
{
Updata(i*2,l,mid,left,mid,c);
Updata(i*2+1,mid+1,r,mid+1,right,c);
}
Pushup(i);
}
int main()
{
for(int i=1;i<=n;i++)
{
}
BuildTree(1,1,n);
bool haha=false;
for(int i=1;i<=m;i++)
{
if(haha)
continue;
Updata(1,1,n,y,z,x);
if(!pd)
{
haha=true;
cout<<"-1"<<endl;
cout<<i<<endl;
}
}
if(pd)
cout<<"0"<<endl;
return 0;
}

• @ 2015-10-05 20:55:32
#include <bits/stdc++.h>

const int MAXN = 1000000 + 5;
using namespace std;
struct classroom {
int need;
int start;
int end;

} crm[MAXN];

int prs[MAXN];
int r[MAXN];
int n, m, sum, ans = 0;

int in() {
int x = 0, f = 1, c = getchar();
while (!isdigit(c)) {
if (c == '-')f = -1;
c = getchar();
}
while (isdigit(c)) {
x = x * 10 + c - '0';
c = getchar();
}
return x * f;
}

bool judge(int mid) {

memset(prs, 0, sizeof(prs));

for (int i = 1; i <= mid; ++i) {
prs[crm[i].start] += crm[i].need;
prs[crm[i].end + 1] -= crm[i].need;
}

sum = 0;
for (int i = 1; i <= n; ++i) {
sum += prs[i];
if (sum > r[i]) {
return false;
}
}
return true;
}

int main() {
n = in();
m = in();
for (int i = 1; i <= n; ++i) {
r[i] = in();
}
for (int i = 1; i <= m; ++i) {
crm[i].need = in();
crm[i].start = in();
crm[i].end = in();
}
int front = 1, back = m;

while (front <= back) {
int mid = (front + back) / 2;
if (judge(mid)) {
front = mid + 1;
} else {
ans = mid;
back = mid - 1;
}
}

if (ans == 0) {
printf("0");
} else {
printf("-1\n%d", ans);
}
return 0;
}

ID
1782

8

8240

1233

15%

12