巧妙數(shù)組或者一維線段樹。
比賽時沒有仔細看題，結(jié)束標記寫錯了，導(dǎo)致TLE了兩次。大致意思是，線段樹長度[0,len]，初始化為0，插入?yún)^(qū)間增量，最后求兩個最大值的位置，一個是從左到右的最大值（遇到的第一個最大值即為所求），一個是從右到左的最大值。
好長時間沒寫線段樹的原因，導(dǎo)致我直接上模板了，結(jié)構(gòu)體變量有點多，寫的不是很好，代碼很長。正式比賽中第一個線段樹。
后來聽說有O（n）的算法，突然就想起來了學(xué)校oj上有一道巧妙運用數(shù)組的題，然后感覺用數(shù)組可以搞，試了一下AC掉了，時間1900+，比線段樹的5000+少多了。。
。
數(shù)組代碼：
#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;
}