@KirinBill
2018-02-26T21:53:47.000000Z
字数 21523
阅读 1411
分块
目录
那么指针的移动有以下三类:
指针:
综上,的移动次数为。
指针:
综上,的移动次数为。
1.[BZOJ 3781] 小B的询问
- 第一道题,说的详细一点;
- 先用一个数组记录序列上的每个点是否加入答案,每次移动指针就调用add
函数,如果当前点加入答案了就删掉,不然就加进去(这是为了兼容后面的树上莫队);
- 用一个桶记录当前区间中每种颜色的出现次数,之后正常计算就行了;
- 每次修改和查询都是计算,所以复杂度为。
代码:
#include <cstdio>
#include <cmath>
#include <algorithm>
using std::sqrt;
using std::sort;
const int MAXN=50005,MAXM=MAXN,MAXK=MAXN;
int m;
int a[MAXN],buc[MAXK];
long long ans[MAXM];
bool use[MAXN];
struct query{
int lp,rp,l_blk;
long long *ans;
static bool cmp(const query &a,const query &b){
return a.l_blk<b.l_blk || (a.l_blk==b.l_blk && a.rp<b.rp);
}
}qry[MAXM];
inline long long sqr(register long long x){return x*x;}
inline void ist(int u){
ans[0]-=sqr(buc[a[u]]);
++buc[a[u]];
ans[0]+=sqr(buc[a[u]]);
}
inline void del(int u){
ans[0]-=sqr(buc[a[u]]);
--buc[a[u]];
ans[0]+=sqr(buc[a[u]]);
}
inline void add(int u){
if(use[u]) del(u),use[u]=false;
else ist(u),use[u]=true;
}
inline void MoCpt(){
sort(qry+1,qry+m+1,query::cmp);
for(int i=1,l=1,r=0;i<=m;++i){
while(l<qry[i].lp) add(l++);
while(l>qry[i].lp) add(--l);
while(r<qry[i].rp) add(++r);
while(r>qry[i].rp) add(r--);
*qry[i].ans=ans[0];
}
}
int main(){
int n,k;
scanf("%d%d%d",&n,&m,&k);
int BLK_SZ=sqrt(n)+0.5;
for(int i=1;i<=n;++i)
scanf("%d",&a[i]);
for(int i=1;i<=m;++i){
scanf("%d%d",&qry[i].lp,&qry[i].rp);
qry[i].l_blk=qry[i].lp/BLK_SZ;
qry[i].ans=&ans[i];
}
MoCpt();
for(int i=1;i<=m;++i)
printf("%lld\n",ans[i]);
return 0;
}
代码:
#include <cstdio>
#include <algorithm>
#include <cmath>
using std::sort;
using std::sqrt;
const int MAXN=50005;
int m;
long long ans;
int cnt[MAXN],col[MAXN];
long long up[MAXN],dwn[MAXN];
bool use[MAXN];
struct query{
int lp,rp,l_blk;
long long *up;
static bool cmp(const query &a,const query &b){
return a.l_blk<b.l_blk || (a.l_blk==b.l_blk && a.rp<b.rp);
}
}qry[MAXN];
template<typename type>
inline type gcd(register type a,register type b){
register type r;
while(b){r=a%b,a=b,b=r;}
return a;
}
inline void ist(int u){
ans-=(long long)cnt[col[u]]*(cnt[col[u]]-1)>>1;
++cnt[col[u]];
ans+=(long long)cnt[col[u]]*(cnt[col[u]]-1)>>1;
}
inline void del(int u){
ans-=(long long)cnt[col[u]]*(cnt[col[u]]-1)>>1;
--cnt[col[u]];
ans+=(long long)cnt[col[u]]*(cnt[col[u]]-1)>>1;
}
inline void add(int u){
if(use[u]) del(u),use[u]=false;
else ist(u),use[u]=true;
}
inline void MoCpt(){
sort(qry+1,qry+m+1,query::cmp);
for(int i=1,l=1,r=0;i<=m;++i){
while(l<qry[i].lp) add(l++);
while(l>qry[i].lp) add(--l);
while(r<qry[i].rp) add(++r);
while(r>qry[i].rp) add(r--);
*qry[i].up=ans;
}
}
int main(){
int n;
scanf("%d%d",&n,&m);
int BLK_SZ=sqrt(n)+0.5;
for(int i=1;i<=n;++i)
scanf("%d",&col[i]);
for(int i=1;i<=m;++i){
scanf("%d%d",&qry[i].lp,&qry[i].rp);
dwn[i]=(long long)(qry[i].rp-qry[i].lp+1)*(qry[i].rp-qry[i].lp)>>1;
qry[i].l_blk=qry[i].lp/BLK_SZ;
qry[i].up=&up[i];
}
MoCpt();
long long gcd;
for(int i=1;i<=m;++i){
gcd=::gcd(up[i],dwn[i]);
printf("%lld/%lld\n",up[i]/gcd,dwn[i]/gcd);
}
return 0;
}
代码:
#include <cstdio>
#include <cmath>
#include <algorithm>
#include <cstring>
using std::sqrt;
using std::sort;
using std::unique;
using std::lower_bound;
const int MAXN=50005,MAXQ=MAXN;
int n,q,ta_n;
int a[MAXN];
long long ans[MAXQ];
struct query{
int lp,rp,l_blk;
long long *ans;
static bool cmp(const query &a,const query &b){
return a.l_blk<b.l_blk || (a.l_blk==b.l_blk && a.rp<b.rp);
}
}qry[MAXQ];
class BIT{
private:
long long c[MAXN];
int lowbit(register int x){return x&-x;}
long long qry(int r){
long long ret=0;
for(;r;r-=lowbit(r))
ret+=c[r];
return ret;
}
public:
void add(int l,int x){
for(;l<=ta_n;l+=lowbit(l))
c[l]+=x;
}
long long qry(int l,int r){return qry(r)-qry(l-1);}
}ta;
inline void MoCpt(){
sort(qry+1,qry+q+1,query::cmp);
for(int i=1,l=1,r=0;i<=q;++i){
while(l<qry[i].lp){
ans[0]-=ta.qry(1,a[l]-1);
ta.add(a[l],-1);
++l;
}
while(l>qry[i].lp){
--l;
ans[0]+=ta.qry(1,a[l]-1);
ta.add(a[l],1);
}
while(r<qry[i].rp){
++r;
ans[0]+=ta.qry(a[r]+1,ta_n);
ta.add(a[r],1);
}
while(r>qry[i].rp){
ans[0]-=ta.qry(a[r]+1,ta_n);
ta.add(a[r],-1);
--r;
}
*qry[i].ans=ans[0];
}
}
inline void decrete(){
static int tmp[MAXN];
memcpy(tmp,a,sizeof(tmp));
sort(tmp+1,tmp+n+1);
ta_n=unique(tmp+1,tmp+n+1)-tmp-1;
for(int i=1;i<=n;++i)
a[i]=lower_bound(tmp+1,tmp+n+1,a[i])-tmp;
}
int main(){
scanf("%d",&n);
int BLK_SZ=sqrt(n)+0.5;
for(int i=1;i<=n;++i)
scanf("%d",&a[i]);
decrete();
scanf("%d",&q);
for(int i=1;i<=q;++i){
scanf("%d%d",&qry[i].lp,&qry[i].rp);
qry[i].l_blk=qry[i].lp/BLK_SZ;
qry[i].ans=&ans[i];
}
MoCpt();
for(int i=1;i<=q;++i)
printf("%lld\n",ans[i]);
return 0;
}
代码:
#include <cstdio>
#include <cmath>
#include <algorithm>
using std::sqrt;
using std::sort;
const int MAXN=100005,MAXM=1000005,MAXSQRTN=320;
int n,m;
int w[MAXN];
bool use[MAXN];
struct answer{
int cnt,tot;
answer(){cnt=tot=0;}
answer& operator +=(const answer &that){
cnt+=that.cnt,tot+=that.tot;
return *this;
}
}ans[MAXM];
struct query{
int lp,rp,l,r,l_blk;
answer *ans;
static bool cmp(const query &a,const query &b){
return a.l_blk<b.l_blk || (a.l_blk==b.l_blk && a.rp<b.rp);
}
}qry[MAXM];
class Block{
private:
int m,BLK_SZ;
int pos[MAXN],buc[MAXN];
struct node{
int l,r;
answer ans;
}d[MAXSQRTN];
answer brute(int l,int r){
answer ret;
for(int i=l;i<=r;++i){
if(buc[i]){
ret.cnt+=buc[i];
++ret.tot;
}
}
return ret;
}
public:
void init(int n){
BLK_SZ=sqrt(n)+0.5;
m=(n-1)/BLK_SZ+1;
for(int i=1;i<=n;++i)
pos[i]=(i-1)/BLK_SZ+1;
for(int i=1;i<=m;++i){
d[i].l=(i-1)*BLK_SZ+1;
d[i].r=i*BLK_SZ;
}
d[m].r=n;
}
void ist(int x){
++d[pos[x]].ans.cnt;
if(buc[x]++==0) ++d[pos[x]].ans.tot;
}
void del(int x){
--d[pos[x]].ans.cnt;
if(--buc[x]==0) --d[pos[x]].ans.tot;
}
answer qry(int l,int r){
answer ret;
if(pos[l]==pos[r]) ret=brute(l,r);
else{
for(int i=pos[l]+1;i<pos[r];++i)
ret+=d[i].ans;
ret+=brute(l,d[pos[l]].r);
ret+=brute(d[pos[r]].l,r);
}
return ret;
}
}blk;
inline void add(int u){
if(use[u]) blk.del(w[u]),use[u]=false;
else blk.ist(w[u]),use[u]=true;
}
inline void MoCpt(){
blk.init(n);
sort(qry+1,qry+m+1,query::cmp);
for(int i=1,l=1,r=0;i<=m;++i){
while(l<qry[i].lp) add(l++);
while(l>qry[i].lp) add(--l);
while(r<qry[i].rp) add(++r);
while(r>qry[i].rp) add(r--);
*qry[i].ans=blk.qry(qry[i].l,qry[i].r);
}
}
int main(){
scanf("%d%d",&n,&m);
int BLK_SZ=sqrt(n)+0.5;
for(int i=1;i<=n;++i)
scanf("%d",&w[i]);
for(int i=1;i<=m;++i){
scanf("%d%d%d%d",&qry[i].lp,&qry[i].rp,&qry[i].l,&qry[i].r);
qry[i].l_blk=qry[i].lp/BLK_SZ;
qry[i].ans=&ans[i];
}
MoCpt();
for(int i=1;i<=m;++i)
printf("%d %d\n",ans[i].cnt,ans[i].tot);
return 0;
}
代码:
#include <cstdio>
#include <cmath>
#include <algorithm>
using std::sqrt;
using std::sort;
const int MAXN=100005,MAXM=1000005,MAXSQRTN=320;
int n,m;
int w[MAXN],ans[MAXM],pos[MAXN];
bool use[MAXN];
struct query{
int lp,rp,l,r;
int *ans;
static bool cmp(const query &a,const query &b){
return pos[a.lp]<pos[b.lp] || (pos[a.lp]==pos[b.lp] && a.rp<b.rp);
}
}qry[MAXM];
class Block{
private:
int m,BLK_SZ;
int buc[MAXN];
struct node{int l,r,ans;}d[MAXSQRTN];
int brute(int l,int r){
int ret=0;
for(int i=l;i<=r;++i){
if(buc[i]) ++ret;
}
return ret;
}
public:
void init(int n){
BLK_SZ=sqrt(n)+0.5;
m=(n-1)/BLK_SZ+1;
for(int i=1;i<=n;++i)
pos[i]=(i-1)/BLK_SZ+1;
for(int i=1;i<=m;++i){
d[i].l=(i-1)*BLK_SZ+1;
d[i].r=i*BLK_SZ;
}
d[m].r=n;
}
void ist(int x){if(buc[x]++==0) ++d[pos[x]].ans;}
void del(int x){if(--buc[x]==0) --d[pos[x]].ans;}
int qry(int l,int r){
int ret=0;
if(pos[l]==pos[r]) ret=brute(l,r);
else{
for(int i=pos[l]+1;i<pos[r];++i)
ret+=d[i].ans;
ret+=brute(l,d[pos[l]].r);
ret+=brute(d[pos[r]].l,r);
}
return ret;
}
}blk;
inline void add(int u){
if(use[u]) blk.del(w[u]),use[u]=false;
else blk.ist(w[u]),use[u]=true;
}
inline void MoCpt(){
blk.init(n);
sort(qry+1,qry+m+1,query::cmp);
for(int i=1,l=1,r=0;i<=m;++i){
while(l<qry[i].lp) add(l++);
while(l>qry[i].lp) add(--l);
while(r<qry[i].rp) add(++r);
while(r>qry[i].rp) add(r--);
*qry[i].ans=blk.qry(qry[i].l,qry[i].r);
}
}
int main(){
scanf("%d%d",&n,&m);
for(int i=1;i<=n;++i)
scanf("%d",&w[i]);
for(int i=1;i<=m;++i){
scanf("%d%d%d%d",&qry[i].lp,&qry[i].rp,&qry[i].l,&qry[i].r);
qry[i].ans=&ans[i];
}
MoCpt();
for(int i=1;i<=m;++i)
printf("%d\n",ans[i]);
return 0;
}
代码:
#include <cstdio>
#include <cmath>
#include <algorithm>
using std::pow;
using std::sort;
const int MAXN=10005,MAXM=MAXN,MAXC=1e6+5;
int qcnt;
int col[MAXN],lastcol[MAXN],buc[MAXC],ans[MAXM];
bool use[MAXN];
struct query{
int tm,lp,rp,l_blk,r_blk;
int *ans;
static bool cmp(const query &a,const query &b){
return a.l_blk<b.l_blk || (a.l_blk==b.l_blk && a.r_blk<b.r_blk || (a.r_blk==b.r_blk && a.tm<b.tm));
}
}qry[MAXM];
struct option{int u,precol,newcol;}opt[MAXM];
inline void ist(int u){if(buc[col[u]]++==0) ++ans[0];}
inline void del(int u){if(--buc[col[u]]==0) --ans[0];}
inline void add(int u){
if(use[u]) del(u),use[u]=false;
else ist(u),use[u]=true;
}
inline void mdf(int u,int c){
if(use[u]) del(u);
col[u]=c;
if(use[u]) ist(u);
}
inline void MoCpt(){
sort(qry+1,qry+qcnt+1,query::cmp);
for(int i=1,l=1,r=0,tm=0;i<=qcnt;++i){
while(tm<qry[i].tm)
++tm,mdf(opt[tm].u,opt[tm].newcol);
while(tm>qry[i].tm)
mdf(opt[tm].u,opt[tm].precol),--tm;
while(l<qry[i].lp) add(l++);
while(l>qry[i].lp) add(--l);
while(r<qry[i].rp) add(++r);
while(r>qry[i].rp) add(r--);
*qry[i].ans=ans[0];
}
}
int main(){
int n,m;
scanf("%d%d",&n,&m);
int BLK_SZ=pow(n,(double)2/3)+0.5;
for(int i=1;i<=n;++i){
scanf("%d",&col[i]);
lastcol[i]=col[i];
}
char cmd;
for(int i=1,x,y,tm=0;i<=m;++i){
scanf("\n%c%d%d",&cmd,&x,&y);
if(cmd=='Q'){
++qcnt;
qry[qcnt].lp=x,qry[qcnt].rp=y;
qry[qcnt].l_blk=x/BLK_SZ;
qry[qcnt].r_blk=y/BLK_SZ;
qry[qcnt].tm=tm;
qry[qcnt].ans=&ans[qcnt];
}
else{
++tm;
opt[tm].u=x,opt[tm].newcol=y;
opt[tm].precol=lastcol[x];
lastcol[x]=y;
}
}
MoCpt();
for(int i=1;i<=qcnt;++i)
printf("%d\n",ans[i]);
return 0;
}
1.[Codeforces 375D] Tree and Queries
代码:
#include <cstdio>
#include <cmath>
#include <algorithm>
using std::sqrt;
using std::sort;
const int MAXN=1e5+5,MAXM=MAXN,MAXK=MAXN,MAXC=MAXN;
int m;
int he[MAXN];
int col[MAXN];
int buc[MAXK],cnt[MAXC];
int ans[MAXM];
int lp[MAXN],rp[MAXN],id[MAXN];
bool use[MAXN];
struct line{int to,nex;}ed[MAXN<<1];
struct query{
int k,lp,rp,l_blk;
int *ans;
static bool cmp(const query &a,const query &b){
return a.l_blk<b.l_blk || (a.l_blk==b.l_blk && a.rp<b.rp);
}
}qry[MAXM];
inline void addE(int u,int v){
static int cnt;
ed[++cnt]=(line){v,he[u]};
he[u]=cnt;
}
void DFS(int u,int fa){
static int idx;
lp[u]=++idx;
id[idx]=u;
for(int i=he[u],v;i;i=ed[i].nex){
v=ed[i].to;
if(v!=fa) DFS(v,u);
}
rp[u]=idx;
}
inline int ist(int u){++buc[++cnt[col[u]]];}
inline void del(int u){--buc[cnt[col[u]]--];}
inline void add(int u){
if(use[u]) del(u),use[u]=false;
else ist(u),use[u]=true;
}
inline void MoCpt(){
sort(qry+1,qry+m+1,query::cmp);
for(int i=1,l=1,r=0;i<=m;++i){
while(l<qry[i].lp) add(id[l++]);
while(l>qry[i].lp) add(id[--l]);
while(r<qry[i].rp) add(id[++r]);
while(r>qry[i].rp) add(id[r--]);
*qry[i].ans=buc[qry[i].k];
}
}
int main(){
int n;
scanf("%d%d",&n,&m);
int BLK_SZ=sqrt(n)+0.5;
for(int i=1;i<=n;++i)
scanf("%d",&col[i]);
for(int i=1,u,v;i<n;++i){
scanf("%d%d",&u,&v);
addE(u,v),addE(v,u);
}
DFS(1,0);
for(int i=1,v;i<=m;++i){
scanf("%d%d",&v,&qry[i].k);
qry[i].lp=lp[v],qry[i].rp=rp[v];
qry[i].l_blk=lp[v]/BLK_SZ;
qry[i].ans=&ans[i];
}
MoCpt();
for(int i=1;i<=m;++i)
printf("%d\n",ans[i]);
return 0;
}
add
函数操作第一次是加入,操作第二次是删除,正好兼容!1.[SPOJ 10707] Count on a tree II
代码:
#include <cstdio>
#include <cmath>
#include <algorithm>
#include <cstring>
using std::sqrt;
using std::sort;
using std::swap;
using std::unique;
using std::lower_bound;
const int MAXN=40005,MAXM=100005;
int n,m;
int he[MAXN],col[MAXN];
int lp[MAXN],rp[MAXN],id[MAXN<<1];
int dfn[MAXN<<1],pos[MAXN],de[MAXN];
int buc[MAXN],ans[MAXM];
bool use[MAXN];
struct line{int to,nex;}ed[MAXN<<1];
struct query{
int lp,rp,l_blk,lca;
int *ans;
static bool cmp(const query &a,const query &b){
return a.l_blk<b.l_blk || (a.l_blk==b.l_blk && a.rp<b.rp);
}
}qry[MAXM];
class SparseTab{
private:
int c[17][MAXN<<1];
public:
void init(int a[],int n){
memcpy(c[0]+1,a+1,n<<2);
for(int i=1,lim=log2(n);i<=lim;++i){
for(int j=1;j+(1<<i)-1<=n;++j){
if(de[c[i-1][j]]<de[c[i-1][j+(1<<i-1)]])
c[i][j]=c[i-1][j];
else c[i][j]=c[i-1][j+(1<<i-1)];
}
}
}
int LCA(int u,int v){
u=pos[u],v=pos[v];
if(u>v) swap(u,v);
int k=log2(v-u+1);
if(de[c[k][u]]<de[c[k][v-(1<<k)+1]])
return c[k][u];
else return c[k][v-(1<<k)+1];
}
}st;
inline void addE(int u,int v){
static int cnt;
ed[++cnt]=(line){v,he[u]};
he[u]=cnt;
}
void DFS(int u,int fa){
static int idx;
de[u]=de[fa]+1;
dfn[++dfn[0]]=u;
pos[u]=dfn[0];
lp[u]=++idx;
id[idx]=u;
for(int i=he[u],v;i;i=ed[i].nex){
v=ed[i].to;
if(v!=fa){
DFS(v,u);
dfn[++dfn[0]]=u;
}
}
rp[u]=++idx;
id[idx]=u;
}
inline void ist(int u){if(buc[col[u]]++==0) ++ans[0];}
inline void del(int u){if(--buc[col[u]]==0) --ans[0];}
inline void add(int u){
u=id[u];
if(use[u]) del(u),use[u]=false;
else ist(u),use[u]=true;
}
inline void MoCpt(){
sort(qry+1,qry+m+1,query::cmp);
for(int i=1,l=1,r=0;i<=m;++i){
while(l<qry[i].lp) add(l++);
while(l>qry[i].lp) add(--l);
while(r<qry[i].rp) add(++r);
while(r>qry[i].rp) add(r--);
if(qry[i].lca) add(qry[i].lca);
*qry[i].ans=ans[0];
if(qry[i].lca) add(qry[i].lca);
}
}
inline void decrete(){
static int tmp[MAXN];
memcpy(tmp,col,sizeof(tmp));
sort(tmp+1,tmp+n+1);
tmp[0]=unique(tmp+1,tmp+n+1)-tmp-1;
for(int i=1;i<=n;++i)
col[i]=lower_bound(tmp+1,tmp+tmp[0]+1,col[i])-tmp;
}
int main(){
scanf("%d%d",&n,&m);
int BLK_SZ=sqrt(n)+0.5;
for(int i=1;i<=n;++i)
scanf("%d",&col[i]);
decrete();
for(int i=1,u,v;i<n;++i){
scanf("%d%d",&u,&v);
addE(u,v),addE(v,u);
}
DFS(1,0);
st.init(dfn,dfn[0]);
for(int i=1,u,v,lca;i<=m;++i){
scanf("%d%d",&u,&v);
lca=st.LCA(u,v);
if(lp[u]>lp[v]) swap(u,v);
if(lca==u){
qry[i].lp=lp[u];
qry[i].rp=lp[v];
}
else{
qry[i].lp=rp[u];
qry[i].rp=lp[v];
qry[i].lca=lp[lca];
}
qry[i].l_blk=qry[i].lp/BLK_SZ;
qry[i].ans=&ans[i];
}
MoCpt();
for(int i=1;i<=m;++i)
printf("%d\n",ans[i]);
return 0;
}
代码:
#include <cstdio>
#include <cmath>
#include <cstring>
#include <algorithm>
using std::pow;
using std::swap;
using std::sort;
const int MAXN=100005,MAXM=MAXN,MAXQ=MAXN;
int qcnt;
int v[MAXM],w[MAXN],col[MAXN],lastcol[MAXN];
int vis[MAXM];
int he[MAXN];
int de[MAXN],dfn[MAXN<<1],pos[MAXN];
int lp[MAXN],rp[MAXN],id[MAXN<<1];
long long ans[MAXQ];
bool use[MAXN];
struct line{int to,nex;}ed[MAXN<<1];
struct option{int u,newcol,precol;}opt[MAXQ];
struct query{
int tm,lp,rp,lca,l_blk,r_blk;
long long *ans;
static bool cmp(const query &a,const query &b){
return a.l_blk<b.l_blk || (a.l_blk==b.l_blk && (a.r_blk<b.r_blk || (a.r_blk==b.r_blk && a.tm<b.tm)));
}
}qry[MAXQ];
class SparseTab{
private:
int c[18][MAXN<<1];
public:
void init(int a[],int n){
memcpy(c[0]+1,a+1,n<<2);
for(int i=1,lim=log2(n);i<=lim;++i){
for(int j=1;j+(1<<i)-1<=n;++j){
if(de[c[i-1][j]]<de[c[i-1][j+(1<<i-1)]])
c[i][j]=c[i-1][j];
else c[i][j]=c[i-1][j+(1<<i-1)];
}
}
}
int LCA(int u,int v){
u=pos[u],v=pos[v];
if(u>v) swap(u,v);
int k=log2(v-u+1);
if(de[c[k][u]]<de[c[k][v-(1<<k)+1]])
return c[k][u];
else return c[k][v-(1<<k)+1];
}
}st;
inline void addE(int u,int v){
static int cnt;
ed[++cnt]=(line){v,he[u]};
he[u]=cnt;
}
void DFS(int u,int fa){
static int idx;
de[u]=de[fa]+1;
dfn[++dfn[0]]=u;
pos[u]=dfn[0];
lp[u]=++idx;
id[idx]=u;
for(int i=he[u],v;i;i=ed[i].nex){
v=ed[i].to;
if(v!=fa){
DFS(v,u);
dfn[++dfn[0]]=u;
}
}
rp[u]=++idx;
id[idx]=u;
}
inline void ist(int u){
ans[0]+=(long long)v[col[u]]*w[++vis[col[u]]];
}
inline void del(int u){
ans[0]-=(long long)v[col[u]]*w[vis[col[u]]--];
}
inline void add(int u){
u=id[u];
if(use[u]) del(u),use[u]=false;
else ist(u),use[u]=true;
}
inline void mdf(int u,int c){
if(use[u]) del(u);
col[u]=c;
if(use[u]) ist(u);
}
inline void MoCpt(){
sort(qry+1,qry+qcnt+1,query::cmp);
for(int i=1,l=1,r=0,tm=0;i<=qcnt;++i){
while(tm<qry[i].tm)
++tm,mdf(opt[tm].u,opt[tm].newcol);
while(tm>qry[i].tm)
mdf(opt[tm].u,opt[tm].precol),--tm;
while(l<qry[i].lp) add(l++);
while(l>qry[i].lp) add(--l);
while(r<qry[i].rp) add(++r);
while(r>qry[i].rp) add(r--);
if(qry[i].lca) add(qry[i].lca);
*qry[i].ans=ans[0];
if(qry[i].lca) add(qry[i].lca);
}
}
int main(){
int n,m,q;
scanf("%d%d%d",&n,&m,&q);
int BLK_SZ=pow(n,(double)2/3)+0.5;
for(int i=1;i<=m;++i)
scanf("%d",&v[i]);
for(int i=1;i<=n;++i)
scanf("%d",&w[i]);
for(int i=1,u,v;i<n;++i){
scanf("%d%d",&u,&v);
addE(u,v),addE(v,u);
}
DFS(1,0);
st.init(dfn,dfn[0]);
for(int i=1;i<=n;++i){
scanf("%d",&col[i]);
lastcol[i]=col[i];
}
for(int i=1,t,x,y,lca,tm=0;i<=q;++i){
scanf("%d%d%d",&t,&x,&y);
if(t==0){
++tm;
opt[tm].u=x;
opt[tm].newcol=y;
opt[tm].precol=lastcol[x];
lastcol[x]=y;
}
else{
++qcnt;
qry[qcnt].tm=tm;
qry[qcnt].ans=&ans[i];
lca=st.LCA(x,y);
if(lp[x]>lp[y]) swap(x,y);
if(lca==x){
qry[qcnt].lp=lp[x];
qry[qcnt].rp=lp[y];
}
else{
qry[qcnt].lp=rp[x];
qry[qcnt].rp=lp[y];
qry[qcnt].lca=lp[lca];
}
qry[qcnt].l_blk=qry[qcnt].lp/BLK_SZ;
qry[qcnt].r_blk=qry[qcnt].rp/BLK_SZ;
}
}
MoCpt();
for(int i=1;i<=q;++i){
if(ans[i]) printf("%lld\n",ans[i]);
}
return 0;
}
2.[BZOJ 4129] Haruna’s Breakfast
代码:
#include <cstdio>
#include <cmath>
#include <algorithm>
#include <cstring>
using std::pow;
using std::sqrt;
using std::sort;
using std::swap;
using std::ceil;
const int MAXN=5e4+5,MAXM=MAXN,MAXSQRTN=225;
int n,qcnt;
int he[MAXN],w[MAXN],lastw[MAXN];
int de[MAXN],pos[MAXN],dfn[MAXN<<1];
int lp[MAXN],rp[MAXN],id[MAXN<<1];
int ans[MAXM];
bool use[MAXN];
struct line{int to,nex;}ed[MAXN<<1];
struct query{
int lp,rp,l_blk,r_blk,tm,lca;
int *ans;
static bool cmp(const query &a,const query &b){
return a.l_blk<b.l_blk || (a.l_blk==b.l_blk && a.r_blk<b.r_blk || (a.r_blk==b.r_blk && a.tm<b.tm));
}
}qry[MAXM];
struct option{int u,prew,neww;}opt[MAXM];
class SparseTab{
private:
int c[17][MAXN<<1];
public:
void init(int a[],int n){
memcpy(c[0]+1,a+1,n<<2);
for(int i=1,lim=log2(n);i<=lim;++i){
for(int j=1;j+(1<<i)-1<=n;++j){
if(de[c[i-1][j]]<de[c[i-1][j+(1<<i-1)]])
c[i][j]=c[i-1][j];
else c[i][j]=c[i-1][j+(1<<i-1)];
}
}
}
int LCA(int u,int v){
u=pos[u],v=pos[v];
if(u>v) swap(u,v);
int k=log2(v-u+1);
if(de[c[k][u]]<de[c[k][v-(1<<k)+1]])
return c[k][u];
else return c[k][v-(1<<k)+1];
}
}st;
class Block{
private:
int n,m,BLK_SZ;
int buc[MAXN];
struct node{
int l,r,cnt;
int size(){return r-l+1;}
}d[MAXSQRTN];
public:
void init(int n){
this->n=n;
BLK_SZ=sqrt(n)+0.5;
m=(n-1)/BLK_SZ+1;
for(int i=1;i<=n;++i)
pos[i]=(i-1)/BLK_SZ+1;
for(int i=1;i<=m;++i){
d[i].l=(i-1)*BLK_SZ+1;
d[i].r=i*BLK_SZ;
}
d[m].r=n;
}
void ist(int x){
if(x<=n && buc[x]++==0)
++d[pos[x]].cnt;
}
void del(int x){
if(x<=n && --buc[x]==0)
--d[pos[x]].cnt;
}
int qry(){
int cur;
for(cur=1;cur<=m;++cur){
if(d[cur].cnt<d[cur].size())
break;
}
for(int i=d[cur].l;i<=d[cur].r;++i){
if(buc[i]==0) return i;
}
}
}blk;
inline void addE(int u,int v){
static int cnt;
ed[++cnt]=(line){v,he[u]};
he[u]=cnt;
}
void DFS(int u,int fa){
static int idx;
de[u]=de[fa]+1;
dfn[++dfn[0]]=u;
pos[u]=dfn[0];
lp[u]=++idx;
id[idx]=u;
for(int i=he[u],v;i;i=ed[i].nex){
v=ed[i].to;
if(v!=fa){
DFS(v,u);
dfn[++dfn[0]]=u;
}
}
rp[u]=++idx;
id[idx]=u;
}
inline void add(int u){
u=id[u];
if(use[u]) blk.del(w[u]),use[u]=false;
else blk.ist(w[u]),use[u]=true;
}
inline void mdf(int u,int x){
if(use[u]) blk.del(w[u]);
w[u]=x;
if(use[u]) blk.ist(w[u]);
}
inline void MoCpt(){
blk.init(n+1);
sort(qry+1,qry+qcnt+1,query::cmp);
for(int i=1,l=1,r=0,tm=0;i<=qcnt;++i){
while(tm<qry[i].tm)
++tm,mdf(opt[tm].u,opt[tm].neww);
while(tm>qry[i].tm)
mdf(opt[tm].u,opt[tm].prew),--tm;
while(l<qry[i].lp) add(l++);
while(l>qry[i].lp) add(--l);
while(r<qry[i].rp) add(++r);
while(r>qry[i].rp) add(r--);
if(qry[i].lca) add(qry[i].lca);
*qry[i].ans=blk.qry();
if(qry[i].lca) add(qry[i].lca);
}
}
int main(){
int m;
scanf("%d%d",&n,&m);
int BLK_SZ=pow(n,(double)2/3)+0.5;
for(int i=1;i<=n;++i){
scanf("%d",&w[i]);
lastw[i]=++w[i];
}
for(int i=1,u,v;i<n;++i){
scanf("%d%d",&u,&v);
addE(u,v),addE(v,u);
}
DFS(1,0);
st.init(dfn,dfn[0]);
for(int i=1,cmd,x,y,tm=0,lca;i<=m;++i){
scanf("%d%d%d",&cmd,&x,&y);
if(cmd==0){
++tm;
opt[tm].u=x,opt[tm].neww=++y;
opt[tm].prew=lastw[x];
lastw[x]=y;
}
else{
++qcnt;
lca=st.LCA(x,y);
if(lp[x]>lp[y]) swap(x,y);
if(lca==x){
qry[qcnt].lp=lp[x];
qry[qcnt].rp=lp[y];
}
else{
qry[qcnt].lp=rp[x];
qry[qcnt].rp=lp[y];
qry[qcnt].lca=lp[lca];
}
qry[qcnt].l_blk=qry[qcnt].lp/BLK_SZ;
qry[qcnt].r_blk=qry[qcnt].rp/BLK_SZ;
qry[qcnt].tm=tm;
qry[qcnt].ans=&ans[qcnt];
}
}
MoCpt();
for(int i=1;i<=qcnt;++i)
printf("%d\n",ans[i]-1);
return 0;
}