#include <iostream>
#include <cstdio>
#include <cstring>
#include <algorithm>
#include <queue>
const int maxn=5e4+4;
int n,q,tt;
int mmx,mmn;
int cow[maxn];
struct Node
{
int mx,mn,l,r;
int getMid() { return (l+r) >> 1; }
}treeN[maxn<<2];
int getMid(int l,int r)
{
return (l+r) >> 1;
}
void build(int l,int r,int root)
{
treeN[root].l=l; treeN[root].r=r;
if(l==r)
{
treeN[root].mx=cow[l];
treeN[root].mn=cow[l];
return;
}
int mmd=getMid(l,r);
build(l,mmd,root<<1);
build(mmd+1,r,(root<<1)+1);
treeN[root].mx=std::max(treeN[root<<1].mx,treeN[(root<<1)+1].mx);
treeN[root].mn=std::min(treeN[root<<1].mn,treeN[(root<<1)+1].mn);
}
void getAns(int l,int r,int root)
{
if(treeN[root].mn>=mmn && treeN[root].mx<=mmx) return ;
if(treeN[root].l==l && treeN[root].r==r)
{
mmx=std::max(mmx,treeN[root].mx);
mmn=std::min(mmn,treeN[root].mn);
return ;
}
int mmd=treeN[root].getMid();
if(r<=mmd) getAns(l,r,root<<1);
else if(l>mmd) getAns(l,r,(root<<1)+1);
else
{
getAns(l,mmd,root<<1);
getAns(mmd+1,r,(root<<1)+1);
}
}
int main()
{
scanf("%d%d",&n,&q);
for(int i=1; i<=n; i++) scanf("%d",&cow[i]);
build(1,n,1);
for(int i=0; i<q; i++)
{
scanf("%d%d",&n,&tt);
mmx=-1,mmn=1000005;
getAns(n,tt,1);
printf("%d\n",mmx-mmn);
}
return 0;
}
#include <iostream>
#include <cstdio>
#include <cmath>
#include <cstdlib>
#include <cstring>
#include <algorithm>
#include <map>
#include <queue>
typedef std::pair<int ,int > PP;
typedef long long ll;
int n,m;
ll ans;
const int maxm=10005;
const int BIG=1e9+7;
int val[maxm];
PP p[maxm];
int treen[maxm<<2],lazy[maxm<<2];
int getMid(int a,int b)
{
return (a+b)>>1;
}
bool cmp(PP a,PP b)
{
if(a.second==b.second) return a.first < b.first;
return a.second < b.second;
}
void build(int l,int r,int rt)
{
lazy[rt]=0;
if(l==r) treen[rt]=val[l];
else
{
int mid=getMid(l,r);
build(l,mid,rt<<1);
build(mid+1,r,rt<<1|1);
treen[rt]=std::min(treen[rt<<1],treen[rt<<1|1]);
}
}
void pushdown(int rt)
{
if(lazy[rt]==0) return ;
lazy[rt<<1]+=lazy[rt];
lazy[rt<<1|1]+=lazy[rt];
treen[rt<<1]-=lazy[rt];
treen[rt<<1|1]-=lazy[rt];
lazy[rt]=0;
}
void update(int l,int r,int sl,int sr,int rt,int val)
{
if(l>=sl && r<=sr) treen[rt]-=val,lazy[rt]+=val;
else
{
pushdown(rt);
int mid=getMid(l,r);
if(mid>=sl) update(l,mid,sl,sr,rt<<1,val);
if(mid<sr) update(mid+1,r,sl,sr,rt<<1|1,val);
treen[rt]=std::min(treen[rt<<1],treen[rt<<1|1]);
}
}
int query(int l,int r,int sl,int sr,int rt)
{
if(l>=sl && r<=sr) return treen[rt];
if(l>sr || r<sl) return BIG;
int mid=getMid(l,r);
int re=BIG;
pushdown(rt);
if(mid<sr) re=std::min(query(mid+1,r,sl,sr,rt<<1|1),re);
if(mid>=sl) re=std::min(query(l,mid,sl,sr,rt<<1),re);
return re;
}
int main()
{
std::cin >> n >> m;
int sn=n-1;
for(int i=0; i<sn; i++) std::cin >> val[i];
build(0,n-2,1);
for(int i=0; i<m; i++)
{
std::cin >> p[i].first >> p[i].second;
if(p[i].first > p[i].second) std::swap(p[i].first,p[i].second);
p[i].second-=1;
}
std::sort(p,p+m,cmp);
ans=0;
for(int i=0; i<m; i++)
{
int tt=query(0,n-2,p[i].first,p[i].second,1);
ans+=tt;
update(0,n-2,p[i].first,p[i].second,1,tt);
}
std::cout << ans;
return 0;
}
Processed:
0.010, SQL:
8
