单身狗之歌配上铃儿响叮当的调贼好听

#include<iostream>
#include<cstdio>
#include<cmath>
#include<cstring>
#include<algorithm>
using namespace std;
const int maxn=1010;
int t,n,q;
int c[maxn][maxn]={0};
int lowbit(int);
int getsum(int ,int);
int gengxin(int,int,int);
char Getchar();
void Init();
int main()
{
scanf("%d",&t);
for(int i=1;i<=t;i++)
{
Init();
}
return 0;
}
void Init()
{
scanf("%d%d",&n,&q);
for(int i=1;i<=q;i++)
{
char ch=Getchar();
if(ch=='C'){
int x1,x2,y1,y2;
scanf("%d%d%d%d",&x1,&y1,&x2,&y2);
gengxin(x1,y1,1);
gengxin(x2+1,y2+1,1);
gengxin(x2+1,y2,-1);
gengxin(x2,y2+1,-1);
}
if(ch=='Q'){
int x1,y1;
scanf("%d%d",&x1,&y1);
int k=getsum(x1,y1);
printf("%d\n",k%2);
}
}
memset(c,0,sizeof(c));
}
char Getchar()
{
char ch;
while(ch=getchar(),ch!='C'&&ch!='Q');
return ch;
}
int lowbit(int x)
{
return x&-x;
}
int getsum(int x,int y)
{
int tot=0;
for(int i=x;i>0;i-=lowbit(i))
for(int j=y;j>0;j-=lowbit(j))
tot+=c[i][j];
return tot;
}
int gengxin(int x,int y,int z)
{
for(int i=x;i<=n;i+=lowbit(i))
for(int j=y;j<=n;j+=lowbit(j))
c[i][j]+=z;
}

建了两个树状数组，一个记录第i只单身狗到目前被攻击的次数，一个记录第i只单身狗到目前受到的伤害吨数。
我们其实可以认为，第i只单身狗每被攻击一次就会回血d[i]。
所以，若一只单身狗被攻击了m次，伤害总吨数t，则现在它的h值即为“初始h”+m*d[i]-t

我这魔性的代码

论超时的缘故____折腾人的快读。。。

压七位可以过，就是这个输出格式略恶心。。我是把压七位的数又展开了，调这个转换的过程WA3次

谁把这个题目改了？时间限制太可怕了！原来做对现在错了，同样的一个程序交了之后评测结果还不一样！

这题有一个数据比数列操作b和数列操作c还强！笨算法超时了。。。

这题跟数列操作b差不多，数据有点弱，我的傻算法也能过。

一位数组直接操作居然也可以，这二星题数据挺弱的。

VIP根据大白书的提示，写n^3的匈牙利算法成功AC！

回复 @liu_runda :
这不是弗洛伊德么？

floyd

第一次见到卡unsigned long long与 long long的，丧心病狂

inf要往死里开...1e15都wa了

你们说这种题有什么意义

e

与1398类似