标签：tmp int 寻找 id -- ans 宝藏 300005
- 树状数组可以用来维护前缀最大值
- 把矩形按某个坐标排序来处理问题的思想
点击查看代码
#include <bits/stdc++.h>
using namespace std;
int p[300005],v[300005],n,m;
long long ans[300005],tmp[300005],f[300005],g[300005],h[300005],c[300005];
struct t1
{
int x1,y1,x2,y2,id;
}t[300005];
int read1()
{
char cc=getchar();
while(!(cc>=48&&cc<=57))
{
if(cc=='-')
{
break;
}
cc=getchar();
}
bool f=false;
int s=0;
if(cc=='-')
{
f=true;
}
else
{
s=cc-48;
}
while(1)
{
cc=getchar();
if(cc>=48&&cc<=57)
{
s=s*10+cc-48;
}
else
{
break;
}
}
if(f==true)
{
s=-s;
}
return s;
}
int lowbit(int n)
{
return n&(-n);
}
void add(int n1,long long va)
{
while(n1<=n)
{
c[n1]=max(c[n1],va);
n1+=lowbit(n1);
}
}
long long ask(int n1)
{
long long s=0;
while(n1>0)
{
s=max(s,c[n1]);
n1-=lowbit(n1);
}
return s;
}
bool cmpx1(t1 a,t1 b)
{
return a.x1<b.x1;
}
bool cmpx2(t1 a,t1 b)
{
return a.x2>b.x2;
}
void solve1()
{
for(int i=1;i<=n;i++)
{
c[i]=0;
}
sort(t+1,t+m+1,cmpx1);
int j=0;
for(int i=1;i<=m;i++)
{
while(j+1<=n&&j+1<t[i].x1)
{
j++;
add(n+1-p[j],h[j]);
}
ans[t[i].id]=max(ans[t[i].id],ask(n+1-(t[i].y2+1)));
}
}
void solve2()
{
for(int i=1;i<=n;i++)
{
c[i]=0;
}
sort(t+1,t+m+1,cmpx2);
int j=n+1;
for(int i=1;i<=m;i++)
{
while(j-1>=1&&j-1>t[i].x2)
{
j--;
add(p[j],h[j]);
}
ans[t[i].id]=max(ans[t[i].id],ask(t[i].y1-1));
}
}
void solve3()
{
for(int i=1;i<=n;i++)
{
c[i]=0;
}
sort(t+1,t+m+1,cmpx1);
int j=0;
for(int i=1;i<=m;i++)
{
while(j+1<=n&&j+1<t[i].x1)
{
j++;
add(p[j],f[j]);
}
tmp[t[i].id]=ask(t[i].y2);
}
for(int i=1;i<=n;i++)
{
c[i]=0;
}
j=n+1;
for(int i=m;i>=1;i--)
{
while(j-1>=1&&j-1>=t[i].x1)
{
j--;
add(n+1-p[j],g[j]);
}
tmp[t[i].id]+=ask(n+1-(t[i].y2+1));
ans[t[i].id]=max(ans[t[i].id],tmp[t[i].id]);
}
}
void solve4()
{
for(int i=1;i<=n;i++)
{
c[i]=0;
}
sort(t+1,t+m+1,cmpx2);
int j=0;
for(int i=m;i>=1;i--)
{
while(j+1<=n&&j+1<=t[i].x2)
{
j++;
add(p[j],f[j]);
}
tmp[t[i].id]=ask(t[i].y1-1);
}
for(int i=1;i<=n;i++)
{
c[i]=0;
}
j=n+1;
for(int i=1;i<=m;i++)
{
while(j-1>=1&&j-1>t[i].x2)
{
j--;
add(n+1-p[j],g[j]);
}
tmp[t[i].id]+=ask(n+1-t[i].y1);
ans[t[i].id]=max(ans[t[i].id],tmp[t[i].id]);
}
}
int main()
{
int T;
cin>>T;
while(T--)
{
cin>>n>>m;
for(int i=1;i<=n;i++)
{
c[i]=0;
}
for(int i=1;i<=n;i++)
{
p[i]=read1();
v[i]=read1();
f[i]=v[i]+ask(p[i]);
add(p[i],f[i]);
}
for(int i=1;i<=n;i++)
{
c[i]=0;
}
for(int i=n;i>=1;i--)
{
g[i]=v[i]+ask(n+1-p[i]);
add(n+1-p[i],g[i]);
h[i]=f[i]+g[i]-v[i];
}
for(int i=1;i<=m;i++)
{
t[i].x1=read1();
t[i].y1=read1();
t[i].x2=read1();
t[i].y2=read1();
t[i].id=i;
}
solve1();
solve2();
solve3();
solve4();
for(int i=1;i<=m;i++)
{
printf("%lld\n",ans[i]);
ans[i]=0;
}
}
return 0;
}
标签：tmp,
int,
寻找,
id,
--,
ans,
宝藏,
300005
From： https://www.cnblogs.com/watersail/p/18332637