NC20540. [CQOI2017]老C的任务
描述
输入描述
第一行两个整数 n, m,表示一共有n个基站和m次查询。接下来一共有n行,每行由xi , yi , pi 三个空格隔开的整数构成,表示一个基站的坐标(xi , yi )和功率pi 。不会有两个基站位于同一坐标。接下来一共有m行,每行由x1j , y1j , x2j , y2j 四个空格隔开的整数构成,表示一次查询的矩形区域。该矩形对角坐标为(x1j , y1j )和(x2j , y2j ),且 4 边与坐标轴平行。2^31 ≤ xi , yi , pi , x1j , y1j , x2j , y2j < 2^31, x1j ≤ x2j, y1j ≤ y2j。
输出描述
输出 m 行,每行一个整数,对应每次查询的结果。
示例1
输入:
4 2 0 0 1 0 1 2 2 2 4 1 0 8 0 0 1 1 1 1 5 6
输出:
11 4
C++14(g++5.4) 解法, 执行用时: 893ms, 内存消耗: 40772K, 提交时间: 2020-03-26 16:55:54
#include <iostream>
#include <algorithm>
using namespace std;
typedef long long ll;
const ll MAXN=1100001;
struct poll{
ll x,y,d,P;
}qr[MAXN],c[MAXN],temp[MAXN];
ll s[MAXN],pos[MAXN];
bool operator<(poll a,poll b)
{
if (a.x!=b.x) return a.x<b.x;
if (a.y!=b.y) return a.y<b.y;
return a.P>b.P;
}
ll n,m;
void mg(ll l,ll r)
{
if (l>=r) return;
// for (ll i=l;i<=r;i++){
// cout<<qr[i].y<<' ';
// }
// cout<<endl;
ll mid=(l+r)/2;
mg(l,mid);
mg(mid+1,r);
ll a1=mid,a2=r;
ll t=r-l+1;
ll rt=0;
while (a1>=l||a2>=mid+1)
{
// cout<<t<<' '<<a1<<' '<<a2<<endl;
if (a1<l){
s[qr[a2].d]+=rt;
temp[t--]=qr[a2--];
continue;
}
if (a2<mid+1)
{
rt+=qr[a1].P;
temp[t--]=qr[a1--];
continue;
}
if (qr[a1].y<=qr[a2].y)
{
rt+=qr[a1].P;
temp[t--]=qr[a1--];
}
else
{
s[qr[a2].d]+=rt;
temp[t--]=qr[a2--];
}
}
//cout<<"t="<<t<<endl;
for (ll i=l;i<=r;i++){
qr[i]=temp[i-l+1];
// cout<<qr[i].y<<' ';
}
// cout<<endl;
}
ll gg(ll x)
{
ll t=1;
while (t<x)
t<<=1;
return t;
}
int main()
{
cin>>n>>m;
for (ll i=1;i<=n;i++){
cin>>qr[i].x>>qr[i].y;
cin>>qr[i].P;
qr[i].d=i;
}
for (ll i=n+1;i<=n+4*m;i+=4)
{
cin>>qr[i].x>>qr[i].y>>qr[i+1].x>>qr[i+1].y;
qr[i].x--;
qr[i].y--;
qr[i+2].x=qr[i].x;
qr[i+2].y=qr[i+1].y;
qr[i+3].x=qr[i+1].x;
qr[i+3].y=qr[i].y;
qr[i].d=i;
qr[i+1].d=i+1;
qr[i+2].d=i+2;
qr[i+3].d=i+3;
qr[i].P=qr[i+1].P=qr[i+2].P=qr[i+3].P=0;
}
sort(qr+1,qr+n+4*m+1);
for (ll i=1;i<=4*m+n;i++){
pos[qr[i].d]=i;
// cout<<qr[i].x<<' '<<qr[i].y<<' '<<qr[i].P<<endl;
}
// for (ll i=1;i<=4*m+n;i++)
// cout<<pos[i]<<' ';
// cout<<endl;
mg(1,4*m+n);
// for (ll i=1;i<=4*m+n;i++)
// cout<<s[i]<<' ';
for (ll i=n+1;i<=n+4*m;i+=4)
cout<<s[i+1]-s[i+2]-s[i+3]+s[i]<<endl;
/* cin>>n;
for (ll i=1;i<=n;i++)
{
cin>>qr[i].y;
qr[i].d=i;
qr[i].P=i;
}
mg(1,n);
for (ll i=1;i<=n;i++)
cout<<qr[i].y<<'-'<<s[i]<<'\n';*/
}
C++(clang++11) 解法, 执行用时: 315ms, 内存消耗: 19168K, 提交时间: 2021-02-14 13:00:06
#include<set>
#include<map>
#include<queue>
#include<stack>
#include<cmath>
#include<vector>
#include<cstdio>
#include<cstring>
#include<iostream>
#include<algorithm>
#define ll long long
using namespace std;
struct node
{
int x;
int y;
int num;
int cnt;
int v;
}s[10000010];
int n,m;
ll v[10000010];
int a,b,c,d;
int g[10000010];
int maxy;
int tot;
ll ans[2000010][5];
void add(int x,int k)
{
for(int i=x;i<=maxy;i+=i&-i)
{
v[i]+=1ll*k;
}
}
ll ask(int x)
{
ll res=0;
for(int i=x;i;i-=i&-i)
{
res+=v[i];
}
return res;
}
bool cmp(node a,node b)
{
if(a.x==b.x)
{
if(a.y==b.y)
{
return a.cnt<b.cnt;
}
return a.y<b.y;
}
return a.x<b.x;
}
int main()
{
scanf("%d%d",&n,&m);
for(int i=1;i<=n;i++)
{
scanf("%d%d%d",&s[i].x,&s[i].y,&s[i].v);
g[i]=s[i].y;
}
tot=n;
for(int i=1;i<=m;i++)
{
scanf("%d%d%d%d",&a,&b,&c,&d);
s[++tot].x=a-1;
s[tot].y=b-1;
s[tot].cnt=i;
s[tot].num=1;
g[tot]=b-1;
s[++tot].x=a-1;
s[tot].y=d;
s[tot].cnt=i;
s[tot].num=2;
g[tot]=d;
s[++tot].x=c;
s[tot].y=b-1;
s[tot].cnt=i;
s[tot].num=3;
g[tot]=b-1;
s[++tot].x=c;
s[tot].y=d;
s[tot].cnt=i;
s[tot].num=4;
g[tot]=d;
}
sort(g+1,g+1+tot);
sort(s+1,s+1+tot,cmp);
maxy=unique(g+1,g+1+tot)-g-1;
for(int i=1;i<=tot;i++)
{
if(!s[i].cnt)
{
int val=lower_bound(g+1,g+1+maxy,s[i].y)-g;
add(val,s[i].v);
}
else
{
int val=lower_bound(g+1,g+1+maxy,s[i].y)-g;
ans[s[i].cnt][s[i].num]=ask(val);
}
}
for(int i=1;i<=m;i++)
{
printf("%lld\n",ans[i][4]+ans[i][1]-ans[i][2]-ans[i][3]);
}
}