about 4 years ago

嘛……因为gty太神了……所以要实现best gene【立个梗0.0】

隔空呼叫可不可以TAT 0w0 好主意!!

【于是伟大善良的zky决定把这个事情做永久记录!让后面的学弟来ym……】

至于1呢……因为太水了所以没交到bzoj上……

于是这道题目竟然过了……过了……过了……

做法1、线段树+每个叶子节点上开一个set,再用map来hash

优点是好想,也是原标程的做法——直到wwx神犇以优良的性能【时间,空间和码长】秒杀

做法2、维护一个set,里面存的是可以做实验的房间。如果要做实验,就把他们都加入到map里。

注意!由于边加入边删除,就要注意set的iterator。而且因为已经删了,就要在外面维护一个ts[],room[]表示当前房间的hash值以及人数。

hash也有个奇妙的方式,每个数rand一个long long ,插入删除只需要异或。

#include<cstdio>
#include<cstring>
#include<cstdlib>
#include<algorithm>
#include<cstdlib>
#include<set>
#include<map>
#define maxn 200101
using namespace std;
int n,m,q,result=0,hashn=0;
int dy[maxn]={0},ts[maxn]={0};
long long seed[maxn]={0};
long long room[maxn]={0};
map<int,int> hash;
struct point
{
public:
int x,num,cnt;
friend bool operator <(const point a,const point b)
{
return a.x<b.x;
}
};
set<point> a;
int readln()
{
char c=getchar();int result=0,bj=1;
while (c!='-'&&!(c<='9'&&c>='0')) c=getchar();
if (c=='-') c=getchar(),bj=-1;
while (c<='9'&&c>='0') result=result*10+c-'0',c=getchar();
return result*bj;
}
int main()
{
// srand(17171);
srand(112);
int i,j,x,y;
point p;
set<point>::iterator k;
char st[5]={0};
n=readln();m=readln();q=readln();
for (i=1;i<=n;i++)
{ dy[i]=1;
seed[i]=(rand()*13131+(long long)rand()*21313+(rand()*7567353+10067));
// seed[i]=((long long)rand()*19+(long long)rand()*17171+(rand()*771+1137));
p.num^=seed[i];
room[1]^=seed[i];
}
p.x=1;ts[1]=p.cnt=n;a.insert(p);
while (q--)
{
scanf("%s",st);
if (st[0]=='C')
{
x=readln();y=readln();
p.x=dy[x];p.num=p.cnt=0;
room[dy[x]]^=seed[x];
--ts[dy[x]];
k=a.find(p);
if (hash.find(room[dy[x]])!=hash.end())
{if (k!=a.end())a.erase(k);}
else
{
p.cnt=ts[dy[x]];
p.num=room[dy[x]];
p.x=dy[x];
if (k!=a.end())a.erase(k);
if (p.cnt!=0) a.insert(p);
}
dy[x]=y;
p.x=y;p.num=p.cnt=0;
room[dy[x]]^=seed[x];
++ts[dy[x]];
k=a.find(p);
if (k!=a.end())
{
if (hash.find(room[dy[x]])!=hash.end())
a.erase(k);
else
{
p.cnt=ts[dy[x]];
p.num=room[dy[x]];
p.x=y;
a.erase(k);
a.insert(p);
}
}
else
{
p.x=y;p.num=room[y];p.cnt=ts[y];
if (hash.find(p.num)==hash.end())
a.insert(p);
}
}
if (st[0]=='W')
{ result=0;
x=readln();y=readln();
p.x=x;p.num=p.cnt=0;
k=a.lower_bound(p);
if (k!=a.end())
while (k->x<=y)
{
result+=k->cnt;
hash[k->num]=++hashn;
a.erase(k);
k=a.lower_bound(p);
if (k==a.end()) break;
}
printf("%d\n",result);
}
}
}
← 【bzoj2322】【gauss】【线性基】梦想封印 【bzoj2668】【费用流】交换棋子 →
 
comments powered by Disqus