组队赛六：线段树离散化+树状数组并哈希
组队赛6：线段树离散化+树状数组并哈希
G题：URAL 1987
这题比赛的时候没看懂题目，现在又研究了好久，把题意理解错了，然后看队友交的代码都不懂，大帝一提醒才知道又把题意看错了^_^.因为把以前的线段树模板给放弃了，采取了更加飘逸的数组写法，所以还不是很熟悉……而且代码是看了别人的，代码与上次保存的代码都差不多，就是处理lazy标记的不一样而已，就是这个不一样，苦死我了，现在那个Pushup函数还没看懂怎么意思……唉……过段时间回来看看应该才懂吧……
#include <iostream>
#include <cstdio>
#include <fstream>
#include <algorithm>
#include <cmath>
#include <deque>
#include <vector>
#include <list>
#include <queue>
#include <string>
#include <cstring>
#include <map>
#include <stack>
#include <set>
#define PI acos(-1.0)
#define mem(a,b) memset(a,b,sizeof(a))
#define sca(a) scanf("%d",&a)
#define sc(a,b) scanf("%d%d",&a,&b)
#define pri(a) printf("%d\n",a)
#define lson i<<1,l,mid
#define rson i<<1|1,mid+1,r
#define MM 1000005
#define MN 200050
#define INF 1000000009
#define eps 1e-7
using namespace std;
typedef long long ll;
int lazy[MN*8],a[MN/2],b[MN/2],c[MN*8],q[MN/2];
void pushdown(int i) //处理lazy标记
{
if(lazy[i]!=-1)
{
lazy[i<<1]=lazy[i<<1|1]=lazy[i];
lazy[i]=-1; //去除标记
}
}
void pushup(int i)
{
if(lazy[i<<1]==lazy[i<<1|1]) lazy[i]=lazy[i<<1]; //不过这句话没看懂
else lazy[i]=-1;
}
void update(int i,int l,int r,int L,int R,int val)
{
if(L<=l&&r<=R) {lazy[i]=val;return ;}
pushdown(i); //处理lazy标记往下传
int mid=(l+r)>>1;
if(L<=mid) update(lson,L,R,val);
if(R>mid) update(rson,L,R,val);
pushup(i);
}
int query(int i,int l,int r,int w)
{
if(l==r) return lazy[i];
pushdown(i); //处理lazy标记往下传
int res,mid=(l+r)>>1;
if(w<=mid) res=query(lson,w);
else res=query(rson,w);
pushup(i);
return res;
}
int main()
{
int n,m,i,cnt=0;
mem(lazy,-1);
sca(n);
for(i=1;i<=n;i++)
{
sc(a[i],b[i]);
c[cnt++]=a[i];
c[cnt++]=b[i];
}
sca(m);
for(i=1;i<=m;i++)
sca(q[i]),c[cnt++]=q[i];
sort(c,c+cnt);
cnt=unique(c,c+cnt)-c; //去重离散化
for(i=1;i<=n;i++)
{
int L=lower_bound(c,c+cnt,a[i])-c+1;
int R=lower_bound(c,c+cnt,b[i])-c+1;
update(1,1,cnt,L,R,i);
}
for(i=1;i<=m;i++)
pri(query(1,1,cnt,lower_bound(c,c+cnt,q[i])-c+1));
return 0;
}
I题：URAL 1989
这题用的字符串哈希方法，以前学了那么多哈希函数，竟然没想到还有字符串哈希这个计算方法，真是没学完啊，哈希的思想太强大了，其实范神他们暴搞的也是用的哈希思想，只不过计算方法不一样罢了，实质还是一样的。然后上网找了好多代码，理解了字符串哈希后，敲了好久都没过，然后照着别人的敲了也没过，靠……原来是敲错了……
参照博客网址：http://www.cnblogs.com/zhsl/p/3395880.html
现在还有点不理解的就是为什么计算sum的时候还要乘上哈希值，这点至今未弄懂……
#include <iostream>
#include <cstdio>
#include <fstream>
#include <algorithm>
#include <cmath>
#include <deque>
#include <vector>
#include <list>
#include <queue>
#include <string>
#include <cstring>
#include <map>
#include <stack>
#include <set>
#define PI acos(-1.0)
#define mem(a,b) memset(a,b,sizeof(a))
#define sca(a) scanf("%d",&a)
#define sc(a,b) scanf("%d%d",&a,&b)
#define pri(a) printf("%d\n",a)
#define lson i<<1,l,mid
#define rson i<<1|1,mid+1,r
#define MM 1000005
#define MN 100050
#define INF 1000000009
#define eps 1e-7
using namespace std;
typedef long long ll;
typedef unsigned long long ULL;
ULL p[MN],s[MN][2]; //unsigned long long 能自动取模还是第一次知道
char str[MN];
int len;
void update(int x,int flag,ULL val)
{
for(int i=x; i<=len; i+=i&(-i))
s[i][flag]+=val;
}
ULL sum(int x,int flag)
{
ULL ans=0;
for(int i=x; i; i-=i&(-i))
ans+=s[i][flag];
return ans;
}
int main()
{
int n,i,a,b;
char c,ss[30];
p[0]=1;
for(i=1; i<MN; i++) p[i]=p[i-1]*27;
scanf("%s",str);
mem(s,0);
len=strlen(str);
for(i=0; i<len; i++)
update(i+1,0,p[i]*(str[i]-'a'+1)),
update(i+1,1,p[i]*(str[len-i-1]-'a'+1)); //字符串反转的哈希值
sca(n);
while(n--)
{
scanf("%s",ss);
if(!strcmp(ss,"change"))
{
scanf("%d %c",&a,&c);
update(a,0,p[a-1]*(c-str[a-1])); //c-str[a-1]是因为刚开始加了str[a-1]所以这里减去才是更新
update(len-a+1,1,p[len-a]*(c-str[a-1]));
str[a-1]=c; //刚开始少了这句话影响后面的更新一直WA靠……这人写得太飘逸了
}
else
{
scanf("%d%d",&a,&b);
ULL sum1=(sum(b,0)-sum(a-1,0))*p[len-b]; //为何还要乘以p[len-b]还不知道
ULL sum2=(sum(len-a+1,1)-sum(len-b,1))*p[a-1];
if(sum1==sum2) puts("Yes");
else puts("No");
}
}
return 0;
}