NC19839. 枇杷
描述
庭有枇杷树，吾妻死之年所手植也，今已亭亭如盖矣。
输入描述
第一行一个整数 n，表示接下来有 n 个操作。
接下来 n 行，每行的格式为 1 x y 或 2 x1 y1 x2 d。
如果第一个数为 1，表示将 (x,y) 的权值加 1。
否则为询问。
输出描述
对于每个询问，输出对应的直角梯形内部的点权和。
示例1
输入:
6 1 1 2 1 1 3 1 3 2 2 1 2 2 1 1 3 4 2 1 2 3 2
输出:
3 4
C++14(g++5.4) 解法, 执行用时: 330ms, 内存消耗: 11620K, 提交时间: 2018-10-22 14:58:20
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int maxn=4e5+10,mod=1e9+7,inf=0x3f3f3f3f;
int n,m,k,t,d[maxn],tot,f[maxn];
int ret[maxn];
void add(int x,int y){while(x<=tot)d[x]+=y,x+=x&(-x);}
void del(int x){while(x<=tot)d[x]=0,x+=x&(-x);}
int get(int x){int ret=0;while(x)ret+=d[x],x-=x&(-x);return ret;}
struct O{int op,x,y,z,w;}q[maxn];
struct P
{
int op,x,y,typ,id;
bool operator<(const P&p)const
{
return x<p.x;
}
}tmp[maxn],p[maxn];
void cdq(int l,int r)
{
if(l==r)return;
int mid=l+r>>1;
cdq(l,mid);
cdq(mid+1,r);
for(int i=l,j=mid+1;i<=mid||j<=r;)
{
if(i<=mid&&(j>r||p[i].x<=p[j].x))
{
if(p[i].op==1)add(p[i].y,1);
i++;
}
else
{
if(p[j].op==2)ret[p[j].id]+=p[j].typ*get(p[j].y);
j++;
}
}
for(int i=l;i<=mid;i++)
if(p[i].op==1)del(p[i].y);
merge(p+l,p+mid+1,p+mid+1,p+r+1,tmp+l);
for(int i=l;i<=r;i++)
p[i]=tmp[i];
}
int main()
{
int i,j;
//freopen("in.txt","r",stdin);
scanf("%d",&n);
for(i=1;i<=n;i++)
{
scanf("%d%d%d",&q[i].op,&q[i].x,&q[i].y);
if(q[i].op==2)
{
scanf("%d%d",&q[i].z,&q[i].w);
p[++m]={q[i].op,q[i].z+q[i].w,q[i].y+q[i].z+q[i].w,1,i};
p[++m]={q[i].op,q[i].z,q[i].y+q[i].z+q[i].w,-1,i};
f[++tot]=q[i].y+q[i].z+q[i].w;
}
else
{
p[++m]={q[i].op,q[i].x,q[i].x+q[i].y,0,i};
f[++tot]=q[i].x+q[i].y;
}
}
sort(f+1,f+tot+1);
tot=unique(f+1,f+tot+1)-f-1;
for(i=1;i<=m;i++)
p[i].y=lower_bound(f+1,f+tot+1,p[i].y)-f;
cdq(1,m);
m=0,tot=0;
for(i=1;i<=n;i++)
{
if(q[i].op==2)
{
p[++m]={q[i].op,q[i].z,q[i].y+q[i].w,1,i};
p[++m]={q[i].op,q[i].z+q[i].w,q[i].y-1,-1,i};
p[++m]={q[i].op,q[i].x-1,q[i].y+q[i].w,-1,i};
p[++m]={q[i].op,q[i].x-1,q[i].y-1,1,i};
f[++tot]=q[i].y+q[i].w;
f[++tot]=q[i].y-1;
}
else
{
p[++m]={q[i].op,q[i].x,q[i].y,0,i};
f[++tot]=q[i].y;
}
}
sort(f+1,f+tot+1);
tot=unique(f+1,f+tot+1)-f-1;
for(i=1;i<=m;i++)
p[i].y=lower_bound(f+1,f+tot+1,p[i].y)-f;
cdq(1,m);
for(i=1;i<=n;i++)
if(q[i].op==2)printf("%d\n",ret[i]);
return 0;
}
C++11(clang++ 3.9) 解法, 执行用时: 380ms, 内存消耗: 63072K, 提交时间: 2018-10-19 20:36:32
#include<bits/stdc++.h>
using namespace std;
#define int long long
const int N=500005;
struct node{
int x,y,z,ans,id;
node(int x=0,int y=0,int z=0,int ans=0,int id=0):x(x),y(y),z(z),ans(ans),id(id){}
bool operator < (const node&a)const{
if(y!=a.y)return y<a.y;
return id<a.id;
}
}a[N],b[N],tmp[N];
int sm[N],c[N],n,ans[N],isqry[N],cnt1,cnt2;
void add(int x,int y){for(;x<N;x+=x&-x)sm[x]+=y;}
int qry(int x){int ans=0;for(;x;x-=x&-x)ans+=sm[x];return ans;}
void solve(int l,int r,node*a){
if(l>r)return;
if(l==r){a[l].id=l;return;}
int mid=(l+r)/2;
solve(l,mid,a);solve(mid+1,r,a);
merge(a+l,a+mid+1,a+mid+1,a+r+1,tmp+l);
for(int i=l;i<=r;i++){
a[i]=tmp[i];
if(!a[i].z&&a[i].id<=mid)add(a[i].x,1);
if(a[i].z&&a[i].id>mid)a[i].ans+=qry(a[i].x);
}
for(int i=l;i<=r;i++)if(!a[i].z&&a[i].id<=mid)add(a[i].x,-1);
}
signed main(){
ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);
cin>>n;
for(int i=1;i<=n;i++){
int op,x,y,x2,d;
cin>>op>>x>>y;
if(op==1){
a[++cnt1]=node(x+y,-y,0);
b[++cnt2]=node(x,y,0);
}else{
cin>>x2>>d;
a[++cnt1]=node(x2+d+y,-y,i);
a[++cnt1]=node(x2+d+y,-(y+d+1),-i);
b[++cnt2]=node(x-1,y+d,-i);
b[++cnt2]=node(x-1,y-1,i);
isqry[i]=1;
}
}
for(int i=1;i<=cnt1;i++)c[i]=a[i].x;
sort(c+1,c+cnt1+1);
for(int i=1;i<=cnt1;i++)a[i].x=lower_bound(c+1,c+cnt1+1,a[i].x)-c;
for(int i=1;i<=cnt2;i++)c[i]=b[i].x;
sort(c+1,c+cnt2+1);
for(int i=1;i<=cnt2;i++)b[i].x=lower_bound(c+1,c+cnt2+1,b[i].x)-c;
solve(1,cnt1,a);solve(1,cnt2,b);
for(int i=1;i<=cnt1;i++)
if(a[i].z>0)ans[a[i].z]+=a[i].ans;
else if(a[i].z<0)ans[-a[i].z]-=a[i].ans;
for(int i=1;i<=cnt2;i++)
if(b[i].z>0)ans[b[i].z]+=b[i].ans;
else if(b[i].z<0)ans[-b[i].z]-=b[i].ans;
for(int i=1;i<=n;i++)
if(isqry[i])cout<<ans[i]<<'\n';
return 0;
}