NC247070. 233的网格图
描述
输入描述
第一行三个正整数
接下来行每行两个正整数代表
接下来行代表操作,格式如题面所写
输出描述
对于每个操作输出一行一个数代表答案
示例1
输入:
4 2 5 1 2 3 4 2 5 6 3 1 3 1 2 3 1 2 2 1
输出:
3 5 6
C++(g++ 7.5.0) 解法, 执行用时: 3363ms, 内存消耗: 834640K, 提交时间: 2022-12-10 12:01:27
#include<bits/stdc++.h>
using namespace std;
template <typename T> inline void read(T &x)
{
x=0;short f=1;char c=getchar();
for(;c<'0'||c>'9';c=getchar()) if(c=='-') f=-1;
for(;c>='0'&&c<='9';c=getchar()) x=(x<<1)+(x<<3)+(c^48);
x*=f;return;
}
const int max_n=1e5+5;
int x[max_n],y[max_n];
const int V=1e4;
const int R=2*V+1;
const int max_R=R+5;
namespace BIT{
int val[max_R][max_R];
inline void add(int x,int y,int v)
{
for(int i=x;i<=R;i+=i&(-i))
for(int j=y;j<=R;j+=j&(-j))
val[i][j]+=v;
}
inline int query(int x,int y)
{
int res=0;
for(int i=x;i>0;i-=i&(-i))
for(int j=y;j>0;j-=j&(-j))
res+=val[i][j];
return res;
}
}
inline int query(int a,int b,int c,int d)
{
a=max(a,1),b=min(b,R),c=max(c,1),d=min(d,R);
if(a>b||c>d)
return 0;
return BIT::query(b,d)-BIT::query(a-1,d)-BIT::query(b,c-1)+BIT::query(a-1,c-1);
}
int n,k,q;
inline int calc(int x,int y)
{
int a1=x-k,b1=x+k,c1=y-k,d1=y+k;
int res=query(a1,b1,c1,d1);
int a=(x+y-V-2)>>1,b=x-a-1;
swap(a,b);
x=a+b+1,y=a-b+V+1;
int a2=x-k,b2=x+k,c2=y-k,d2=y+k;
res+=query(a2,b2,c2,d2);
res-=query(max(a1,a2),min(b1,b2),max(c1,c2),min(d1,d2));
return res;
}
long long ans;
inline void calc()
{
ans=0;
for(int i=1;i<=n;++i)
ans+=calc(x[i],y[i]);
}
int main()
{
scanf("%d%d%d",&n,&k,&q);
for(int i=1;i<=n;++i)
{
int a,b;
scanf("%d%d",&a,&b);
x[i]=a+b+1,y[i]=a-b+V+1;
BIT::add(x[i],y[i],1);
}
calc();
const int lim=2e4;
while(q--)
{
int opt;
scanf("%d",&opt);
if(opt==1)
{
if(k<=lim)
printf("%lld\n",(ans-n)>>1);
else
printf("%lld\n",n*(n-1ll)>>1);
}
else if(opt==2)
{
int u;
scanf("%d",&u);
if(u==1)
continue;
if(k<=lim)
{
k*=u;
if(k<=lim)
calc();
}
}
else
{
int o,a,b;
scanf("%d%d%d",&o,&a,&b);
if(k<=lim)
{
ans-=calc(x[o],y[o])*2-1;
BIT::add(x[o],y[o],-1);
x[o]=a+b+1,y[o]=a-b+V+1;
BIT::add(x[o],y[o],1);
ans+=calc(x[o],y[o])*2-1;
}
}
}
return 0;
}
C++(clang++ 11.0.1) 解法, 执行用时: 3902ms, 内存消耗: 832492K, 提交时间: 2022-12-09 21:48:32
#include<bits/stdc++.h>
using namespace std;
const int max_n=1e5+5;
int x[max_n],y[max_n];
const int V=1e4;
const int R=2*V+1;
const int max_R=R+5;
namespace BIT
{
int val[max_R][max_R];
inline void add(int x,int y,int v)
{
for(int i=x;i<=R;i+=i&(-i))
for(int j=y;j<=R;j+=j&(-j))
val[i][j]+=v;
}
inline int query(int x,int y)
{
int res=0;
for(int i=x;i>0;i-=i&(-i))
for(int j=y;j>0;j-=j&(-j))
res+=val[i][j];
return res;
}
}
inline int query(int a,int b,int c,int d)
{
a=max(a,1),b=min(b,R),c=max(c,1),d=min(d,R);
if(a>b||c>d)
return 0;
return BIT::query(b,d)-BIT::query(a-1,d)-BIT::query(b,c-1)+BIT::query(a-1,c-1);
}
int n,k,q;
inline int calc(int x,int y)
{
int a1=x-k,b1=x+k,c1=y-k,d1=y+k;
int res=query(a1,b1,c1,d1);
int a=(x+y-V-2)>>1,b=x-a-1;
swap(a,b);
x=a+b+1,y=a-b+V+1;
int a2=x-k,b2=x+k,c2=y-k,d2=y+k;
res+=query(a2,b2,c2,d2);
res-=query(max(a1,a2),min(b1,b2),max(c1,c2),min(d1,d2));
return res;
}
long long ans;
inline void calc()
{
ans=0;
for(int i=1;i<=n;++i)
ans+=calc(x[i],y[i]);
}
int main()
{
// fprintf(stderr,"sizeof(val)=%d\n",(int)sizeof(BIT::val));
// freopen("input.txt","r",stdin);
// freopen("output.txt","w",stdout);
scanf("%d%d%d",&n,&k,&q);
for(int i=1;i<=n;++i)
{
int a,b;
scanf("%d%d",&a,&b);
x[i]=a+b+1,y[i]=a-b+V+1;
BIT::add(x[i],y[i],1);
}
calc();
// fprintf(stderr,"Time: %d ms\n",(int)clock());
const int lim=2e4;
while(q--)
{
// if(q>1e5-1000)
// fprintf(stderr,"q=%d\n",q);
int opt;
scanf("%d",&opt);
if(opt==1)
{
if(k<=lim)
printf("%lld\n",(ans-n)>>1);
else
printf("%lld\n",n*(n-1ll)>>1);
}
else if(opt==2)
{
int u;
scanf("%d",&u);
if(u==1)
continue;
if(k<=lim)
{
k*=u;
if(k<=lim)
calc();
}
}
else
{
int o,a,b;
scanf("%d%d%d",&o,&a,&b);
if(k<=lim)
{
ans-=calc(x[o],y[o])*2-1;
BIT::add(x[o],y[o],-1);
x[o]=a+b+1,y[o]=a-b+V+1;
BIT::add(x[o],y[o],1);
ans+=calc(x[o],y[o])*2-1;
}
}
}
return 0;
}