宁波建网站推荐,昆明网站建设云集创,深圳公司排名前100名,使用asp.net制作网站的整体过程前言
当暴力思路与题解中的“暴力”不同时#xff0c;继续想优化往往就渐行渐远了… 所以当没有头绪时#xff0c;要勇于跳出原有的转化#xff01;
这种位运算类型的优化似乎始终不在我的寄存器中…需要加强#xff01;
解析
不难想到按位考虑的 O(nklog2n)O(nk\log…前言
当暴力思路与题解中的“暴力”不同时继续想优化往往就渐行渐远了… 所以当没有头绪时要勇于跳出原有的转化
这种位运算类型的优化似乎始终不在我的寄存器中…需要加强
解析
不难想到按位考虑的 O(nklog2n)O(nk\log^2n)O(nklog2n) 的树剖做法LCT可以单log。 考虑这样的实现f0/1f_{0/1}f0/1 表示某一位原来是 0/1 目前的值。 合并fopfr,fl,opf_{op}f_{r,f_{l,op}}fopfr,fl,op 可以写成如下形式fop(fl,opfr,1)∣((fl,op⊕1)fr,0)f_{op}(f_{l,op}\f_{r,1})|((f_{l,op}\oplus1)\f_{r,0})fop(fl,opfr,1)∣((fl,op⊕1)fr,0)。 那么我们就可以把 64 个布尔压成一个 unsigned long long从而进行快速合并。 这样就把复杂度的 k 拿掉了时间复杂度 O(nlog2n)O(n\log^2n)O(nlog2n)。
代码
1ulli 写成 1i WA了半天…
#includebits/stdc.h
#includestring
using namespace std;
#define ll long long
#define ull unsigned ll
#define debug(...) fprintf(stderr,__VA_ARGS__)
#define ok debug(OK\n)inline ll read() {ll x(0),f(1);char cgetchar();while(!isdigit(c)) {if(c-) f-1;cgetchar();}while(isdigit(c)) {x(x1)(x3)c-0;cgetchar();}return x*f;
}
const int N1e5100;
const int mod998244353;bool mem1;int n,m,k;int op[N];
ull w[N],o;
int dep[N],siz[N],hson[N],top[N],fa[N],dfn[N],pos[N],tim;
vectorinte[N];
void dfs1(int x,int f){siz[x]1;dep[x]dep[f]1;fa[x]f;for(int to:e[x]){if(tof) continue;dfs1(to,x);if(siz[to]siz[hson[x]]) hson[x]to;siz[x]siz[to];}return;
}
void dfs2(int x,int tp){top[x]tp;dfn[tim]x;pos[x]tim;if(hson[x]) dfs2(hson[x],tp);for(int to:e[x]){if(tofa[x]||tohson[x]) continue;dfs2(to,to);}return;
}#define mid ((lr)1)
#define ls (k1)
#define rs (k1|1)
struct node{ull w[2];
};
node operator (const node x,const node y){node o;o.w[0](x.w[0]y.w[1])|((~x.w[0])y.w[0]);o.w[1](x.w[1]y.w[1])|((~x.w[1])y.w[0]);return o;
}
node tr1[N2],tr2[N2];
inline void pushup(int k){tr1[k]tr1[ls]tr1[rs];tr2[k]tr2[rs]tr2[ls];
}
void build(int k,int l,int r){if(lr){int xdfn[l];if(op[x]1){tr1[k]tr2[k](node){0,w[x]};}else if(op[x]2){tr1[k]tr2[k](node){w[x],o};}else if(op[x]3){tr1[k]tr2[k](node){w[x],o^w[x]};}//printf(k%d (%d %d) %llu %llu\n,k,l,r,tr1[k].w[0],tr1[k].w[1]);return;}build(ls,l,mid);build(rs,mid1,r);pushup(k);//printf(k%d (%d %d) %llu %llu\n,k,l,r,tr1[k].w[0],tr1[k].w[1]);
}
void upd(int k,int l,int r,int p){if(lr){int xdfn[l];if(op[x]1){tr1[k]tr2[k](node){0,w[x]};}else if(op[x]2){tr1[k]tr2[k](node){w[x],o};}else if(op[x]3){tr1[k]tr2[k](node){w[x],o^w[x]};}return;}if(pmid) upd(ls,l,mid,p);else upd(rs,mid1,r,p);pushup(k);
}
node ask(int k,int l,int r,int x,int y,int op){//if(k1) printf(ask: (%d %d) op%d\n,x,y,op);if(xlry){if(op1) return tr1[k];else return tr2[k];}if(ymid) return ask(ls,l,mid,x,y,op);else if(xmid) return ask(rs,mid1,r,x,y,op);else if(op1) return ask(ls,l,mid,x,y,op)ask(rs,mid1,r,x,y,op);else return ask(rs,mid1,r,x,y,op)ask(ls,l,mid,x,y,op);
}
#undef mid
#undef ls
#undef rsnode query(int x,int y){node res1(node){0,o},res2(node){0,o};while(top[x]!top[y]){if(dep[top[x]]dep[top[y]]){res1res1ask(1,1,n,pos[top[x]],pos[x],2);xfa[top[x]];}else{res2ask(1,1,n,pos[top[y]],pos[y],1)res2;yfa[top[y]];}}if(dep[x]dep[y]) res1res1ask(1,1,n,pos[y],pos[x],2);else res2ask(1,1,n,pos[x],pos[y],1)res2;return res1res2;
} bool mem2;
signed main() {
#ifndef ONLINE_JUDGEfreopen(a.in,r,stdin);freopen(a.out,w,stdout);
#endifnread();mread();kread();if(k0) o0;else{o1;for(int i0;ik;i) o(o1)|1;}for(int i1;in;i) scanf(%d%llu,op[i],w[i]);for(int i1;in;i){int xread(),yread();e[x].push_back(y);e[y].push_back(x);}dfs1(1,0);dfs2(1,1);build(1,1,n);for(int i1;im;i){int oop,x,y;ull z;scanf(%d%d%d%llu,oop,x,y,z);if(oop2){op[x]y;w[x]z;upd(1,1,n,pos[x]);}else{node oquery(x,y);//printf(%llu %llu\n,o.w[0],o.w[1]);ull res(0);for(int ik-1;i0;i--){if(o.w[0](1i)) res(1i);else if((o.w[1](1i))z(1i)){z-(1i);res(1i);}}printf(%llu\n,res);}}return 0;
}
/*3 12 3 3 11 1
*/
