海外网站优化,自媒体wordpress,工信部网站首页,网站域名怎么查询备案价格思路#xff1a; 感觉这题也可神了.. #xff08;还是我太弱#xff09; 首先发现每一位不会互相影响#xff0c;可以把每一位分开考虑#xff0c;然后用树链剖分或者LCT维护这个树 修改直接修改#xff0c;询问的时候算出来每一位填0#xff0c;1经过这条链的变换之后得…思路 感觉这题也可神了.. 还是我太弱 首先发现每一位不会互相影响可以把每一位分开考虑然后用树链剖分或者LCT维护这个树 修改直接修改询问的时候算出来每一位填01经过这条链的变换之后得到的值 考虑贪心从高往低如果这一位填0可以得到1那么填0一定是最优的 否则如果可以填1就把这一位填为1 复杂度是nklog^2n或者nklogn只能通过50%的数据 发现可以并行计算这k位复杂度降为nlog^2n的树链剖分或者nlogn的LCT可以通过100%的数据 这个题没有卡常合并信息不是O( 1 )的算法没有通过是很正常的吧。。。 还有树链剖分没法做到logn每条链建线段树也是log^2n的还不能搞子树似乎常数也一般。。。 最优复杂度是log^2n不过期望下大概是lognloglogn的感觉 这个题的最优复杂度为O( n q( logn k ) )至少目前来说是这样的 from 洛谷的题解. unsigned long long 各种位运算 线段树要分别维护向上的和向下的 //By SiriusRen
#include cstdio
#include cstring
#include algorithm
using namespace std;
const int N100005;
typedef unsigned long long ull;
ull a[N],zz,now,ans;
int n,m,k,op,xx,yy,Op[N],first[N],next[N*2],v[N*2],tot;
int size[N],fa[N],son[N],deep[N],rev[N],dfn[N],cnt,top[N];
struct Tree{ull v0,v1;Tree(){}Tree(int op,ull x){if(op1)v00,v1x;else if(op2)v0x,v1~0;else v0x,v1(~0)^x;}Tree(ull x,ull y){v0x,v1y;}
}trl[N*8],trr[N*8];
Tree operator(Tree x,Tree y){return Tree((x.v0y.v1)|((~x.v0)y.v0),(x.v1y.v1)|((~x.v1)y.v0));}
void add(int x,int y){v[tot]y,next[tot]first[x],first[x]tot;}
void dfs(int x){size[x]1;for(int ifirst[x];~i;inext[i])if(v[i]!fa[x]){fa[v[i]]x,deep[v[i]]deep[x]1,dfs(v[i]),size[x]size[v[i]];if(size[v[i]]size[son[x]])son[x]v[i];}
}
void dfs2(int x,int tp){rev[dfn[x]cnt]x;top[x]tp;if(son[x])dfs2(son[x],tp);for(int ifirst[x];~i;inext[i])if(v[i]!fa[x]v[i]!son[x])dfs2(v[i],v[i]);
}
void build(int l,int r,int pos){if(lr){trl[pos]trr[pos]Tree(Op[rev[l]],a[rev[l]]);return;}int mid(lr)1,lsonpos1,rsonpos1|1;build(l,mid,lson),build(mid1,r,rson);trl[pos]trl[lson]trl[rson],trr[pos]trr[rson]trr[lson];
}
void insert(int l,int r,int pos,int num){if(lr){trl[pos]trr[pos]Tree(Op[rev[l]],a[rev[l]]);return;}int mid(lr)1,lsonpos1,rsonpos1|1;if(midnum)insert(mid1,r,rson,num);else insert(l,mid,lson,num);trl[pos]trl[lson]trl[rson],trr[pos]trr[rson]trr[lson];
}
Tree query(int l,int r,int pos,int L,int R,int f){if(lLrR)return f?trr[pos]:trl[pos];int mid(lr)1,lsonpos1,rsonpos1|1;if(midL)return query(mid1,r,rson,L,R,f);else if(midR)return query(l,mid,lson,L,R,f);else{if(!f)return query(l,mid,lson,L,R,f)query(mid1,r,rson,L,R,f);else return query(mid1,r,rson,L,R,f)query(l,mid,lson,L,R,f);}
}
Tree solve(int x,int y){Tree vxTree((int)3,0ull),vyTree((int)3,0ull);int fxtop[x],fytop[y];while(fx!fy)if(deep[fx]deep[fy])vxvxquery(1,n,1,dfn[fx],dfn[x],1),xfa[fx],fxtop[x];else vyquery(1,n,1,dfn[fy],dfn[y],0)vy,yfa[fy],fytop[y];if(deep[x]deep[y])return vxquery(1,n,1,dfn[y],dfn[x],1)vy;return vxquery(1,n,1,dfn[x],dfn[y],0)vy;
}
int main(){memset(first,-1,sizeof(first)),deep[1]1;scanf(%d%d%d,n,m,k);for(int i1;in;i)scanf(%d%llu,Op[i],a[i]);for(int i1;in;i)scanf(%d%d,xx,yy),add(xx,yy),add(yy,xx);dfs(1),dfs2(1,1),build(1,n,1);while(m--){scanf(%d%d%d%llu,op,xx,yy,zz);if(op2)Op[xx]yy,a[xx]zz,insert(1,n,1,dfn[xx]);else{Tree tsolve(xx,yy);nowans0;for(int ik-1;~i;i--)if(t.v0(1ulli))ans1ulli;else if(t.v1(1ulli)now(1ulli)zz)now1ulli,ans1ulli;printf(%llu\n,ans);}}
} 转载于:https://www.cnblogs.com/SiriusRen/p/6685529.html
