巧妙数组或者一维线段树。
比赛时没有仔细看题，结束标记写错了，导致TLE了两次。大致意思是，线段树长度[0,len]，初始化为0，插入区间增量，最后求两个最大值的位置，一个是从左到右的最大值（遇到的第一个最大值即为所求），一个是从右到左的最大值。
好长时间没写线段树的原因，导致我直接上模板了，结构体变量有点多，写的不是很好，代码很长。正式比赛中第一个线段树。
后来听说有O（n）的算法，突然就想起来了学校oj上有一道巧妙运用数组的题，然后感觉用数组可以搞，试了一下AC掉了，时间1900+，比线段树的5000+少多了。。
。
数组代码：
#include<iostream>
#include<cstdio>
#include<cstring>
using namespace std;
const int MAXM=15003;
int a[MAXM];
int main()
{
int n;
while(scanf("%d",&n)!=EOF)
{
int l,r,b;
memset(a,0,
sizeof(a));
while(scanf("%d %d %d",&l,&r,&b))
{
if(l==-1)
break;
a[l]+=b;
a[r+1]-=b;
}
int lmax=a[0],posl=0;
for(
int i=1;i<=n;i++)
{
a[i]+=a[i-1];
if(lmax<a[i])
{
lmax=a[i];
posl=i;
}
}
int posr;
for(
int i=n;i>=0;i--)
{
if(a[i]==lmax)
{
posr=i;
break;
}
}
printf("%d %d\n",posl,posr);
}
return 0;
}
线段树代码：
#include<iostream>
#include<cstdio>
using namespace std;
inline int L(int r){return r<<1;}
inline int R(int r){return (r<<1)+1;}
inline int MID(int l,int r){return (l+r)>>1;}
const int MAXN=15003;
typedef struct
{
int left,right;
int _max,posl,posr;
int add;
}Node;
Node tree[MAXN*4];
//int arr[MAXN];
void Create(int l,int r,int root)
{
tree[root].left=l;
tree[root].right=r;
if(l==r)
{
tree[root]._max=0;
tree[root].posl=l;
tree[root].posr=r;
tree[root].add=0;
return;
}
int mid=MID(l,r);
Create(l,mid,L(root));
Create(mid+1,r,R(root));
tree[root]._max=0;
tree[root].posl=l;
tree[root].posr=r;
tree[root].add=0;
}
void Update_info(int node)
{
if(tree[node].add)
{
tree[L(node)].add+=tree[node].add;//更新子树时会用到
tree[R(node)].add+=tree[node].add;
tree[L(node)]._max+=tree[node].add;
tree[R(node)]._max+=tree[node].add;
tree[node].add=0;
}
}
void Updata(int l,int r,int val,int root)
{
if(l<=tree[root].left&&tree[root].right<=r)
{
tree[root].add+=val;
tree[root]._max+=val;
return;
}
Update_info(root);
if(tree[root].left==tree[root].right) return;
int mid=(tree[root].left+tree[root].right)>>1;
if(l>mid) Updata(l,r,val,(root<<1)+1);
else if(r<=mid) Updata(l,r,val,root<<1);
else
{
Updata(l,mid,val,root<<1);
Updata(mid+1,r,val,(root<<1)+1);
}
if(tree[L(root)]._max>tree[R(root)]._max)
{
tree[root]._max=tree[L(root)]._max;
tree[root].posl=tree[L(root)].posl;
tree[root].posr=tree[L(root)].posr;
}
else if(tree[L(root)]._max==tree[R(root)]._max)
{
tree[root]._max=tree[L(root)]._max;
tree[root].posl=tree[L(root)].posl;
tree[root].posr=tree[R(root)].posr;
}
else
{
tree[root]._max=tree[R(root)]._max;
tree[root].posl=tree[R(root)].posl;
tree[root].posr=tree[R(root)].posr;
}
}
int main()
{
int n;
while(scanf("%d",&n)!=EOF)
{
int l,r,b;
Create(0,n,1);
while(scanf("%d %d %d",&l,&r,&b))
{
if(l==-1) break;
Updata(l,r,b,1);
}
printf("%d %d\n",tree[1].posl,tree[1].posr);
}
return 0;
}