/category/ds/ zh-CN Thu, 25 May 2017 20:24:07 +0800 Thu, 25 May 2017 20:24:07 +0800 /archives/236/ /archives/236/ Thu, 25 May 2017 20:24:07 +0800 admin ###Description 给一棵树，每个点点权 $$a_i$$，保证 $$a_i$$各不相同，现在随机选两个点 $$u,v$$，求 $$f(u,v)=\phi(a_u\cdot a_v)\cdot dis(u,v)$$ 的期望，$$mod\ 10^9+7$$。 链接：[http://codeforces.com/contest/809/problem/E](http://codeforces.com/contest/809/problem/E "http://codeforces.com/contest/809/problem/E") ###Solution 首先，有一个结论：$$\phi(a\cdot b)=\frac{\phi(a)\cdot\phi(b)\cdot g}{\phi(g)},g=gcd(a,b)$$ 证明：考虑找一个 $$x$$，使得 $$x|b,gcd(\frac{b}{x},a)=1,gcd(x,\frac{b}{x})=1$$ 且 $$a$$ 包含 $$x$$ 中所有质因子。 那么 $$\phi(a\cdot b)=\phi(a)\cdot x\cdot\phi(\frac{b}{x})=\frac{\phi(a)\cdot\phi(b)\cdot x}{\phi(x)}$$ 显然，$$x$$ 是 $$g$$ 的倍数，所以 $$\frac{x}{g}=\frac{\phi(x)}{\phi(g)}$$，所以$$\phi(a\cdot b)=\frac{\phi(a)\cdot\phi(b)\cdot g}{\phi(g)}$$ 有了这个结论之后可以考虑点分，那么设 $$dis(x)$$ 表示 $$x$$ 到当前根的距离。 设 $$h(x)=\frac{x}{\phi(x)}$$，那么$$f(u,v)=\phi(a_u)\cdot\phi(a_v)\cdot h(g)\cdot(dis(u)+dis(v)),g=gcd(a_u,a_v)$$ 考虑当 $$u$$ 确定时，需要知道 $$\sum\phi(a_v)\cdot h(gcd(a_u,a_v))$$ 和 $$\sum\phi(a_v)\cdot h(gcd(a_u,a_v))\cdot dis(v)$$。 设 $$g(x)=h(x)-\sum[y|x,y\neq x]g(y)$$，那么 $$h(gcd(a_u,a_v))=\sum[x|a_u,x|a_v]g(x)$$ 这样就可以直接枚举约数算贡献了。 ###Code ```c++ #include<bits/stdc++.h> typedef long long ll; inline void repr(int&a,int b){if(a<b)a=b;} #define mset(a,b) memset(a,b,sizeof(a)) #define fo0(i,n) for(int i=0,i##end=n;i<i##end;i++) #define fo1(i,n) for(int i=1,i##end=n;i<=i##end;i++) #define fo(i,a,b) for(int i=a,i##end=b;i<=i##end;i++) #define foe(i,x)for(__typeof(x.end())i=x.begin();i!=x.end();++i) const int N=200007,P=1000000007; struct edge { int to;edge*ne; }_e[N*2],*e=_e,*p[N]; inline void add(int a,int b) { *e=(edge){b,p[a]};p[a]=e++; } std::vector<int>v[N]; int n,pr[N],pm,phi[N],inv[N],f[N],w[N],sz[N],rsz,nro,nsz,g[N],h[N],q[N],qe,ans; bool vis[N]; inline void dfs1(int x,int fa) { sz[x]=1; for(edge*i=p[x];i;i=i->ne) if(i->to!=fa&&!vis[i->to]) { dfs1(i->to,x); sz[x]+=sz[i->to]; } } inline void dfs2(int x,int fa) { int t=rsz-sz[x]; for(edge*i=p[x];i;i=i->ne) if(i->to!=fa&&!vis[i->to]) { repr(t,sz[i->to]); dfs2(i->to,x); } if(t<nsz)nsz=t,nro=x; } inline void set(int x,int y,int z) { if(!~g[x])q[qe++]=x,g[x]=h[x]=0; g[x]=(g[x]+(ll)y*f[x])%P; h[x]=(h[x]+(ll)z*f[x])%P; } inline void get(int x,int&y,int&z) { if(~g[x])y=g[x],z=h[x]; else y=z=0; } inline void dfs3(int x,int fa,int dis) { int a=phi[w[x]],b=(ll)a*dis%P; foe(i,v[w[x]])set(*i,a,b); for(edge*i=p[x];i;i=i->ne) if(i->to!=fa&&!vis[i->to]) dfs3(i->to,x,dis+1); } inline void dfs4(int x,int fa,int dis) { int a=phi[w[x]],b=(ll)a*dis%P,A,B; foe(i,v[w[x]]) { get(*i,A,B); ans=(ans+(ll)a*B+(ll)b*A)%P; } for(edge*i=p[x];i;i=i->ne) if(i->to!=fa&&!vis[i->to]) dfs4(i->to,x,dis+1); } inline void work(int x) { dfs1(x,0); rsz=nsz=sz[x],nro=x; dfs2(x,0); vis[x=nro]=1; foe(i,v[w[x]])set(*i,phi[w[x]],0); for(edge*i=p[x];i;i=i->ne) if(!vis[i->to]) { dfs4(i->to,x,1); dfs3(i->to,x,1); } fo0(i,qe)g[q[i]]=h[q[i]]=-1; qe=0; for(edge*i=p[x];i;i=i->ne) if(!vis[i->to])work(i->to); } int main() { fo1(i,N-1)for(int j=i;j<N;j+=i)v[j].push_back(i); fo(i,2,N-1) { if(!vis[i])pr[pm++]=i,phi[i]=i-1; for(int j=0;i*pr[j]<N;j++) { vis[i*pr[j]]=1; if(i%pr[j]==0) { phi[i*pr[j]]=phi[i]*pr[j]; break; } phi[i*pr[j]]=phi[i]*(pr[j]-1); } } phi[1]=1; inv[1]=1; fo(i,2,N-1)inv[i]=(ll)(P-P/i)*inv[P%i]%P; fo1(i,N-1) { f[i]=(ll)i*inv[phi[i]]%P; foe(j,v[i])if(i^*j)(f[i]+=P-f[*j])%=P; } scanf("%d",&n); fo1(i,n)scanf("%d",w+i); fo0(i,n-1) { int x,y; scanf("%d%d",&x,&y); add(x,y); add(y,x); } mset(vis,0); mset(g,0xff); mset(h,0xff); work(1); ans=(ll)ans*inv[n]%P*inv[n-1]%P*2%P; printf("%d",ans); } ``` ]]> 1 /archives/236/#comments /feed/archives/236/ /archives/163/ /archives/163/ Sun, 08 Jan 2017 00:20:00 +0800 admin ###Description 给定一个长度为n的正整数数列a[i]。 定义2个位置的graze值为两者位置差与数值差的和，即graze(x,y)=|x-y|+|a[x]-a[y]|。 2种操作（k都是正整数）： 1.Modify x k：将第x个数的值修改为k。 2.Query x k：询问有几个i满足graze(x,i)<=k。因为可持久化数据结构的流行，询问不仅要考虑当前数列，还要考虑任意历史版本，即统计任意位置上出现过的任意数值与当前的a[x]的graze值<=k的对数。（某位置多次修改为同样的数值，按多次统计） ###Input 第1行两个整数n,q。分别表示数列长度和操作数。 第2行n个正整数，代表初始数列。 第3--q+2行每行一个操作。 ###Output 对于每次询问操作，输出一个非负整数表示答案 ###Sample Input 3 5 2 4 3 Query 2 2 Modify 1 3 Query 2 2 Modify 1 2 Query 1 1 ###Sample Output 2 3 3 ###HINT N<=60000 修改操作数<=40000 询问<=60000 Max{a[i]}含修改<=100000 ###Solution 这道题其实是维护两种操作，向平面上加点，查询菱形内点数 把(x,y)变为(x+y,x-y)，菱形就变成了正方形 假设某个询问是以(x0,y0)为中心，边长为2k的正方形，那么可以拆成两个，一个是x>=x0-k且x<=x0+k且y<=y0+k的点数，另一个是x>=x0-k且x<=x0+k且y<y0-k的点数，把两个询问做差就和原询问相同 那么可以CDQ分治，按y排序，x用树状数组维护 ###Code ```c++ #include<bits/stdc++.h> using namespace std; int n,m,s[60001],ans[60000],ac,qc,mx; struct query { int x,y,k,id;char op; }q[230000],tmp[230000]; inline void add(int x,int y){q[qc].x=x+y,q[qc].y=x-y,qc++,mx=max(mx,x+y);} int p[160001]; inline void pl(int x){for(;x<=mx;x+=x&-x)p[x]++;} inline int qr(int x){if(x<=0)return 0;int r=0;for(x=min(x,mx);x;x^=x&-x)r+=p[x];return r;} inline void cl(int x){for(;x<=mx;x+=x&-x)p[x]=0;} void work(int l,int r) { if(l==r)return; int mid=(l+r)>>1; work(l,mid),work(mid+1,r); int i1=l,i2=mid+1,ti=l; for(;i2<=r;tmp[ti++]=q[i2++]) { for(;i1<=mid&&q[i1].y<=q[i2].y;tmp[ti++]=q[i1++]) if(!q[i1].op)pl(q[i1].x); if(q[i2].op) { if(q[i2].op==1) ans[q[i2].id]+=qr(q[i2].x+q[i2].k)-qr(q[i2].x-q[i2].k-1); else ans[q[i2].id]+=qr(q[i2].x-q[i2].k-1)-qr(q[i2].x+q[i2].k); } } for(;i1<=mid;tmp[ti++]=q[i1++]); for(i1=l;i1<=mid;i1++)if(!q[i1].op)cl(q[i1].x); for(i1=l;i1<=r;i1++)q[i1]=tmp[i1]; } int main() { scanf("%d%d",&n,&m); for(int i=1;i<=n;i++) scanf("%d",s+i),add(i,s[i]); char tmp[10];int a,b; while(m--) { scanf("%s%d%d",tmp,&a,&b); if(tmp[0]=='M') add(a,s[a]=b); else { int x=a+s[a],y=a-s[a]; q[qc].x=x,q[qc].y=y+b,q[qc].k=b,q[qc].id=ac,q[qc].op=1,qc++; q[qc].x=x,q[qc].y=y-b-1,q[qc].k=b,q[qc].id=ac,q[qc].op=2,qc++; ac++; } } work(0,qc-1); for(int i=0;i<ac;i++) printf("%d\n",ans[i]); } ``` ]]> 0 /archives/163/#comments /feed/archives/163/ /archives/149/ /archives/149/ Fri, 16 Dec 2016 15:59:00 +0800 admin ###Description 小A想做一棵很大的树，但是他手上的材料有限，只好用点小技巧了。开始，小A只有一棵结点数为N的树，结点的编号为1,2,…,N，其中结点1为根；我们称这颗树为模板树。小A决定通过这棵模板树来构建一颗大树。构建过程如下：（1）将模板树复制为初始的大树。（2）以下(2.1)(2.2)(2.3)步循环执行M次（2.1）选择两个数字a,b，其中1<=a<=N，1<=b<=当前大树的结点数。（2.2）将模板树中以结点a为根的子树复制一遍，挂到大树中结点b的下方(也就是说，模板树中的结点a为根的子树复制到大树中后，将成为大树中结点b的子树)。（2.3）将新加入大树的结点按照在模板树中编号的顺序重新编号。例如，假设在进行2.2步之前大树有L个结点，模板树中以a为根的子树共有C个结点，那么新加入模板树的C个结点在大树中的编号将是L+1,L+2,…,L+C；大树中这C个结点编号的大小顺序和模板树中对应的C个结点的大小顺序是一致的。下面给出一个实例。假设模板树如下图： ![11(4).png][1] 根据第(1)步，初始的大树与模板树是相同的。在(2.1)步，假设选择了a=4，b=3。运行(2.2)和(2.3)后，得到新的大树如下图所示 ![22(2).png][2] 现在他想问你，树中一些结点对的距离是多少。 ###Input 第一行三个整数：N,M,Q，以空格隔开，N表示模板树结点数，M表示第(2)中的循环操作的次数，Q 表示询问数量。接下来N-1行，每行两个整数 fr,to，表示模板树中的一条树边。再接下来M行，每行两个整数x,to，表示将模板树中 x 为根的子树复制到大树中成为结点to的子树的一次操作。再接下来Q行，每行两个整数fr,to，表示询问大树中结点 fr和 to之间的距离是多少。N,M,Q<=100000 ###Output 输出Q行，每行一个整数，第 i行是第 i个询问的答案。 ###Sample Input 5 2 3 1 4 1 3 4 2 4 5 4 3 3 2 6 9 1 8 5 3 ###Sample Output 6 3 3 ###Solution 先对模板树求lca，并按dfs序建一棵主席树 每次向大树上加子树时，先二分查找他的父亲在哪一块，然后在主席树上查接到哪个节点下面 对于每一块，存它的根节点与根节点的父亲在模板树中的编号 然后把每一块视做节点，可以得到一棵大树，对大树也求lca 处理查询时，需要分3种情况：在同一块中，两块在一条链上，两块不在一条链上 ###Code ```c++ #include<bits/stdc++.h> typedef unsigned char uchar; typedef unsigned int uint; typedef long long ll; typedef unsigned long long ull; typedef double db; typedef long double ldb; #define xx first #define yy second template<typename T> inline T max(T a,T b){return a>b?a:b;} template<typename T> inline T min(T a,T b){return a<b?a:b;} template<typename T> inline T abs(T a){return a>0?a:-a;} template<typename T> inline void repr(T &a,T b){if(a<b)a=b;} template<typename T> inline void repl(T &a,T b){if(a>b)a=b;} template<typename T> inline T sqr(T x){return x*x;} #define mp(a,b) std::make_pair(a,b) #define pb push_back #define lb(x) ((x)&(-(x))) #define N 100000 namespace zx { struct node { int lc,rc,cnt; }s[2000000]; int sm=1; int modify(int x,int l,int r,int p) { int t=sm++; s[t]=s[x]; s[t].cnt++; if(l^r) { int f=(l+r)>>1; if(p<=f) s[t].lc=modify(s[x].lc,l,f,p); else s[t].rc=modify(s[x].rc,f+1,r,p); } return t; } int kth(int a,int b,int l,int r,int k) { if(l==r)return l; int t=s[s[a].lc].cnt-s[s[b].lc].cnt,f=(l+r)>>1; if(t>=k)return kth(s[a].lc,s[b].lc,l,f,k); return kth(s[a].rc,s[b].rc,f+1,r,k-t); } int root[N+1]; } int n,m,q; namespace t1 { int p[N+1],idm,id[N+1],idr[N+1],fa[N+1][17],dep[N+1],sz[N+1]; struct edge { int to,ne; }e[N<<1]; inline void add(int x,int a,int b) { e[x].to=b,e[x].ne=p[a],p[a]=x; } void dfs(int x) { sz[x]=1; id[x]=++idm; zx::root[id[x]]=zx::modify(zx::root[id[x]-1],1,n,x); for(int i=p[x];i;i=e[i].ne) if(e[i].to^fa[x][0]) fa[e[i].to][0]=x,dep[e[i].to]=dep[x]+1,dfs(e[i].to),sz[x]+=sz[e[i].to]; idr[x]=idm; } inline int dis(int x,int y) { int a=x,b=y,ret=0; if(dep[a]<dep[b]) { for(int i=16;~i;i--) if((dep[b]-dep[a])&(1<<i)) ret+=1<<i,b=fa[b][i]; } else if(dep[a]>dep[b]) { for(int i=16;~i;i--) if((dep[a]-dep[b])&(1<<i)) ret+=1<<i,a=fa[a][i]; } if(a==b)return ret; for(int i=16;~i;i--) if(fa[a][i]^fa[b][i]) a=fa[a][i],b=fa[b][i],ret+=1<<i+1; return ret+2; } } namespace t2 { int cnt=1; ll id[N+1],nid; struct data { int a,b,dep,fa[17],di[17]; }s[N+1]; inline void link(int a,ll b) { int c=std::upper_bound(id,id+cnt,b)-id-1; int cf=s[c].a,d=zx::kth(zx::root[t1::idr[cf]],zx::root[t1::id[cf]-1],1,n,b-id[c]+1); s[cnt].a=a; s[cnt].b=d; s[cnt].dep=s[c].dep+1; s[cnt].fa[0]=c; s[cnt].di[0]=t1::dis(cf,d)+1; id[cnt]=nid; nid+=t1::sz[a]; cnt++; } inline void init() { for(int i=0;i<16;i++) for(int j=0;j<cnt;j++) s[j].fa[i+1]=s[s[j].fa[i]].fa[i],s[j].di[i+1]=s[j].di[i]+s[s[j].fa[i]].di[i]; } inline int lca(int x,int y) { int a=x,b=y; if(s[a].dep<s[b].dep) { for(int i=16;~i;i--) if((s[b].dep-s[a].dep)&(1<<i)) b=s[b].fa[i]; } else if(s[a].dep>s[b].dep) { for(int i=16;~i;i--) if((s[a].dep-s[b].dep)&(1<<i)) a=s[a].fa[i]; } if(a==b)return a; for(int i=16;~i;i--) if(s[a].fa[i]^s[b].fa[i]) a=s[a].fa[i],b=s[b].fa[i]; return s[a].fa[0]; } inline ll linkdis(int p,int q,int x,int y) { ll ret=t1::dis(x,s[p].a)+1; for(int i=16;~i;i--) if((s[p].dep-s[q].dep-1)&(1<<i)) ret+=s[p].di[i],p=s[p].fa[i]; return ret+t1::dis(s[p].b,y); } inline ll dis(ll x,ll y) { int p=std::upper_bound(id,id+cnt,x)-id-1,q=std::upper_bound(id,id+cnt,y)-id-1; int xid=zx::kth(zx::root[t1::idr[s[p].a]],zx::root[t1::id[s[p].a]-1],1,n,x-id[p]+1); int yid=zx::kth(zx::root[t1::idr[s[q].a]],zx::root[t1::id[s[q].a]-1],1,n,y-id[q]+1); if(p==q)return t1::dis(xid,yid); int t=lca(p,q); if(t==p)return linkdis(q,p,yid,xid); if(t==q)return linkdis(p,q,xid,yid); ll ret=t1::dis(xid,s[p].a)+t1::dis(yid,s[q].a)+2; for(int i=16;~i;i--) if((s[p].dep-s[t].dep-1)&(1<<i)) ret+=s[p].di[i],p=s[p].fa[i]; for(int i=16;~i;i--) if((s[q].dep-s[t].dep-1)&(1<<i)) ret+=s[q].di[i],q=s[q].fa[i]; return ret+t1::dis(s[p].b,s[q].b); } } int main() { scanf("%d%d%d",&n,&m,&q); for(int i=1;i<n;i++) { int a,b; scanf("%d%d",&a,&b); t1::add(i<<1,a,b); t1::add(i<<1|1,b,a); } zx::root[0]=zx::sm++; t1::fa[1][0]=1; t1::dfs(1); for(int i=0;i<16;i++) for(int j=1;j<=n;j++) t1::fa[j][i+1]=t1::fa[t1::fa[j][i]][i]; t2::s[0].a=1; t2::id[0]=1; t2::nid=n+1; while(m--) { int a; ll b; scanf("%d%lld",&a,&b); t2::link(a,b); } t2::init(); while(q--) { ll a,b; scanf("%lld%lld",&a,&b); printf("%lld\n",t2::dis(a,b)); } } ``` [1]: /usr/uploads/2016/12/1348856476.png [2]: /usr/uploads/2016/12/2791822739.png ]]> 0 /archives/149/#comments /feed/archives/149/ /archives/97/ /archives/97/ Sun, 11 Dec 2016 14:51:00 +0800 admin [传送门][1] [传送门][2] [传送门][3] 题目大意：单点加，矩阵查询 直接上kdtree就好了，定期暴力重构 1176题代码： ```c++ #include<bits/stdc++.h> typedef unsigned char uchar; typedef unsigned int uint; typedef long long ll; typedef unsigned long long ull; typedef double db; typedef long double ldb; #define xx first #define yy second template<typename T> inline T max(T a,T b){return a>b?a:b;} template<typename T> inline T min(T a,T b){return a<b?a:b;} template<typename T> inline T abs(T a){return a>0?a:-a;} template<typename T> inline void repr(T &a,T b){if(a<b)a=b;} template<typename T> inline void repl(T &a,T b){if(a>b)a=b;} template<typename T> T gcd(T a,T b){if(b)return gcd(b,a%b);return a;} template<typename T> T sqr(T x){return x*x;} #define mp(a,b) std::make_pair(a,b) #define pb push_back #define lb(x) ((x)&(-(x))) namespace kd { const int D=2,inf=1000000000; char dnow; struct point { int d[D],val; int operator[](int x){return d[x];} }; inline bool operator<(point a,point b) { return a[dnow]<b[dnow]; } inline int dis(point a,point b){int ret=0;for(int i=0;i<D;i++)ret+=abs(a[i]-b[i]);return ret;} struct kdnode { point p; int sum,l[D],r[D],lc,rc; }; int ans,tm=2; point q1,q2,Q,*P; kdnode t[200010]; inline void update(int k) { for(int i=0;i<D;i++) { if(t[k].lc)repl(t[k].l[i],t[t[k].lc].l[i]),repr(t[k].r[i],t[t[k].lc].r[i]); if(t[k].rc)repl(t[k].l[i],t[t[k].rc].l[i]),repr(t[k].r[i],t[t[k].rc].r[i]); } t[k].sum=t[k].p.val+t[t[k].lc].sum+t[t[k].rc].sum; } inline void init(int x) { for(int i=0;i<D;i++)t[x].l[i]=t[x].r[i]=t[x].p[i];t[x].sum=t[x].p.val; } int build(int l,int r,char now) { if(now==D)now=0; dnow=now; int mid=(l+r)>>1,x=tm++; std::nth_element(P+l,P+mid,P+r+1); t[x].p=P[mid]; t[x].lc=t[x].rc=0; init(x); if(l<mid)t[x].lc=build(l,mid-1,now+1); if(r>mid)t[x].rc=build(mid+1,r,now+1); update(x);return x; } void insert(int k,char now) { if(now==D)now=0; if(Q[now]>=t[k].p[now]) { if(t[k].rc) insert(t[k].rc,now+1); else { t[k].rc=tm++;t[t[k].rc].p=Q; init(t[k].rc); } } else { if(t[k].lc) insert(t[k].lc,now+1); else { t[k].lc=tm++;t[t[k].lc].p=Q; init(t[k].lc); } } update(k); } void query(int k,char now) { if(now==D)now=0; bool tag=1; for(int i=0;i<D;i++) if(q1.d[i]>t[k].l[i]||q2.d[i]<t[k].r[i]) tag=0; if(tag){ans+=t[k].sum;return;} tag=1; for(int i=0;i<D;i++) if(q1.d[i]>t[k].p.d[i]||q2.d[i]<t[k].p.d[i]) tag=0; if(tag)ans+=t[k].p.val; tag=1; for(int i=0;i<D;i++) if(now==i) { if(q1.d[i]>t[k].p.d[i]||q2.d[i]<t[k].l[i])tag=0; } else { if(q1.d[i]>t[k].r[i]||q2.d[i]<t[k].l[i])tag=0; } if(tag&&t[k].lc)query(t[k].lc,now+1); tag=1; for(int i=0;i<D;i++) if(now==i) { if(q1.d[i]>t[k].r[i]||q2.d[i]<t[k].p.d[i])tag=0; } else { if(q1.d[i]>t[k].r[i]||q2.d[i]<t[k].l[i])tag=0; } if(tag&&t[k].rc)query(t[k].rc,now+1); } inline void build(point *p,int n){P=p;build(0,n-1,0);} inline int query(point a,point b){ans=0;q1=a,q2=b;query(1,0);return ans;} inline void insert(point p){Q=p;insert(1,0);} } kd::point pp[200000]; int main() { int cx,n=0,opt; kd::point a,b; scanf("%d%*d",&cx); while(1) { scanf("%d",&opt); if(opt==1) { scanf("%d%d%d",&pp[n].d[0],&pp[n].d[1],&pp[n].val); kd::insert(pp[n++]); } else if(opt==2) { scanf("%d%d%d%d",&a.d[0],&a.d[1],&b.d[0],&b.d[1]); printf("%d\n",kd::query(a,b)+cx*(a.d[1]-a.d[0]+1)*(b.d[1]-b.d[0]+1)); } else return 0; if(n>0&&n%10000==0)kd::tm=1,kd::build(pp,n); } } ``` 过不了就适当调参 [1]: http://www.lydsy.com/JudgeOnline/problem.php?id=1176 [2]: http://www.lydsy.com/JudgeOnline/problem.php?id=2683 [3]: http://www.lydsy.com/JudgeOnline/problem.php?id=4066 ]]> 0 /archives/97/#comments /feed/archives/97/ /archives/96/ /archives/96/ Mon, 05 Dec 2016 13:02:00 +0800 admin ###Description 采药人的药田是一个树状结构，每条路径上都种植着同种药材。 采药人以自己对药材独到的见解，对每种药材进行了分类。大致分为两类，一种是阴性的，一种是阳性的。 采药人每天都要进行采药活动。他选择的路径是很有讲究的，他认为阴阳平衡是很重要的，所以他走的一定是两种药材数目相等的路径。采药工作是很辛苦的，所以他希望他选出的路径中有一个可以作为休息站的节点（不包括起点和终点），满足起点到休息站和休息站到终点的路径也是阴阳平衡的。他想知道他一共可以选择多少种不同的路径。 ###Input 第1行包含一个整数N。 接下来N-1行，每行包含三个整数a_i、b_i和t_i，表示这条路上药材的类型。 ###Output 输出符合采药人要求的路径数目。 ###Sample Input 7 1 2 0 3 1 1 2 4 0 5 2 0 6 3 1 5 7 1 ###Sample Output 1 ###HINT 对于100%的数据，N ≤ 100,000。 ###Solution 点分治，边权为0变成-1，dfs时记前缀和，休息站就判之前有没有出现过该权值，注意处理根节点 ###Code ```c++ #include<bits/stdc++.h> typedef unsigned char uchar; typedef unsigned int uint; typedef long long ll; typedef unsigned long long ull; typedef double db; typedef long double ldb; #define xx first #define yy second template<typename T> inline T max(T a,T b){return a>b?a:b;} template<typename T> inline T min(T a,T b){return a<b?a:b;} template<typename T> inline T abs(T a){return a>0?a:-a;} template<typename T> inline void repr(T &a,T b){if(a<b)a=b;} template<typename T> inline void repl(T &a,T b){if(a>b)a=b;} template<typename T> T gcd(T a,T b){if(b)return gcd(b,a%b);return a;} #define mp(a,b) std::make_pair(a,b) #define pb push_back #define lb(x) ((x)&(-(x))) #define sqr(x) ((x)*(x)) int n,p[100001],em=1,sz[100001],ro,nro,apr[200000],cnt[200000][2]; ll ans; bool vis[100001]; struct edge { int to,ne,w; }e[200000]; inline void add(int a,int b,int w) { e[em].to=b,e[em].ne=p[a],e[em].w=w,p[a]=em++; } void dfs1(int x,int fa) { sz[x]=1; for(int i=p[x];i;i=e[i].ne) if(!vis[e[i].to]&&e[i].to!=fa) dfs1(e[i].to,x),sz[x]+=sz[e[i].to]; } void dfs2(int x,int fa) { bool ok=sz[ro]<=2*sz[x]; for(int i=p[x];i;i=e[i].ne) if(!vis[e[i].to]&&e[i].to!=fa) { dfs2(e[i].to,x); if(sz[e[i].to]*2>sz[ro])ok=0; } if(ok)nro=x; } void dfs3(int x,int fa,int len) { if(len) { if(apr[len+n]) ans+=cnt[n-len][0]; else ans+=cnt[n-len][1]; } else { if(apr[len+n]) ans+=cnt[n][0]+1; else ans+=cnt[n][0]; } apr[len+n]++; for(int i=p[x];i;i=e[i].ne) if(!vis[e[i].to]&&e[i].to!=fa) dfs3(e[i].to,x,len+e[i].w); apr[len+n]--; } void dfs4(int x,int fa,int len) { if(len) { if(apr[len+n]) cnt[n+len][0]++,cnt[n+len][1]++; else cnt[n+len][0]++; } else { cnt[n][0]++; } apr[len+n]++; for(int i=p[x];i;i=e[i].ne) if(!vis[e[i].to]&&e[i].to!=fa) dfs4(e[i].to,x,len+e[i].w); apr[len+n]--; } void dfs5(int x,int fa,int len) { cnt[n+len][0]=cnt[n+len][1]=0; for(int i=p[x];i;i=e[i].ne) if(!vis[e[i].to]&&e[i].to!=fa) dfs5(e[i].to,x,len+e[i].w); } void solve(int x) { dfs1(x,0); ro=x; dfs2(x,0); vis[nro]=1; for(int i=p[nro];i;i=e[i].ne) if(!vis[e[i].to])dfs3(e[i].to,0,e[i].w),dfs4(e[i].to,0,e[i].w); dfs5(nro,0,0); for(int i=p[nro];i;i=e[i].ne) if(!vis[e[i].to])solve(e[i].to); } int main() { scanf("%d",&n); for(int i=1;i<n;i++) { int a,b,c; scanf("%d%d%d",&a,&b,&c); add(a,b,c?c:-1),add(b,a,c?c:-1); } solve(1); printf("%lld\n",ans); } ``` ]]> 0 /archives/96/#comments /feed/archives/96/ /archives/90/ /archives/90/ Thu, 01 Dec 2016 20:46:00 +0800 admin ###Description 敌方有n台人形兵器，每台的攻击力为Ai，护甲值为Di。我方只有一台人形兵器，攻击力为ATK。战斗看作回合制， 每回合进程如下： ·1 我方选择对方某台人形兵器并攻击，令其护甲值减少ATK，若护甲值<0则被破坏。 ·2 敌方每台未被破坏的人形兵器攻击我方基地造成Ai点损失。 但是，在第一回合开始之前，某两台敌方的人形兵器被干掉了(秒杀）。问最好情况下，我方基地会受到多少点损 失。 ###Input 第一行两个数n，ATK，表示敌方人形兵器数量和我方人形兵器攻击力。 接下来n行，每行两个数A，Di，表示对方第i台人形兵器的攻击力和护甲值。 3<=n<=3×10^5，Ai，Di<=10^4，ATK<10^4 ###Output 只一行，一个数，表示最好情况下我方基地会受到的损失总和。 ###Sample Input 3 7 30 8 7 35 1 209 ###Sample Output 28 ###Solution 每个敌人被杀所需时间为 Ti=Di/atk+1 设T的前缀和为P，A的后缀和为S 假设没有秒杀，按Ti/Ai排序后依次杀即可，每个敌人对答案的贡献为Si\*Ti-Ai 假设（排序后）秒杀了i和j（假设i<j） 那么我方损失会减少 Si\*Ti + P(i-1)\*Ai - Ai + Sj\*Tj + P(j-1)\*Aj - Aj - Ti\*Aj 注意最后 -Ti\*Aj 是因为算了两次 由于只有 Ti\*Aj 与 i,j 均有关，这个表达式可以看成一个以Ti为变量的一次函数 若从后往前扫，就可以看成动态维护一些直线的凸包 这个用线段树就可以维护，每个节点存一条直线，标记永久化 修改时，找到两直线交点，把距端点更短的一部分pushdown 查询时把路径上所有节点取max ###Code ```c++ #include<bits/stdc++.h> typedef unsigned char uchar; typedef unsigned int uint; typedef long long ll; typedef unsigned long long ull; typedef double db; typedef long double ldb; #define xx first #define yy second template<typename T> inline T max(T a,T b){return a>b?a:b;} template<typename T> inline T min(T a,T b){return a<b?a:b;} template<typename T> inline T abs(T a){return a>0?a:-a;} template<typename T> inline void repr(T &a,T b){if(a<b)a=b;} template<typename T> inline void repl(T &a,T b){if(a>b)a=b;} template<typename T> T gcd(T a,T b){if(b)return gcd(b,a%b);return a;} #define mp(a,b) std::make_pair(a,b) #define pb push_back #define lb(x) ((x)&(-(x))) #define sqr(x) ((x)*(x)) struct line { ll k,b; }s[35000]; void modify(int x,int l,int r,line p) { if(s[x].k==p.k) { repr(s[x].b,p.b); return; } int t=(l+r)>>1; db f=(db)(p.b-s[x].b)/(s[x].k-p.k); if(f<l||f>r||l==r) { if(p.k*t+p.b>s[x].k*t+s[x].b)s[x]=p; return; } if(f<t+0.5) { if(p.k*r+p.b>s[x].k*r+s[x].b)std::swap(s[x],p); modify(x<<1,l,t,p); } else { if(p.k*l+p.b>s[x].k*l+s[x].b)std::swap(s[x],p); modify(x<<1|1,t+1,r,p); } } ll query(int x,int l,int r,int p) { ll ret=s[x].k*p+s[x].b; if(l!=r) { int t=(l+r)>>1; if(p<=t) repr(ret,query(x<<1,l,t,p)); else repr(ret,query(x<<1|1,t+1,r,p)); } return ret; } struct yjq { int a,t; ll as,tp; inline bool operator <(const yjq &x)const { return (ll)x.a*t<(ll)a*x.t; } }p[300000]; int n,atk; int main() { scanf("%d%d",&n,&atk); for(int i=0;i<n;i++) scanf("%d%d",&p[i].a,&p[i].t),p[i].t=(p[i].t-1)/atk+1; std::sort(p,p+n); for(int i=1;i<n;i++) p[i].tp=p[i-1].tp+p[i-1].t; p[n-1].as=p[n-1].a; for(int i=n-2;i>=0;i--) p[i].as=p[i+1].as+p[i].a; for(int i=0;i<35000;i++) s[i].b=-1e18; ll ta=0; for(int i=n-1;i>=0;i--) { ll tmp=p[i].as*p[i].t+p[i].tp*p[i].a-p[i].a; repr(ta,query(1,1,10000,p[i].t)+tmp); modify(1,1,10000,(line){-p[i].a,tmp}); } ll ans=0; for(int i=0;i<n;i++) ans+=p[i].as*p[i].t-p[i].a; ans-=ta; printf("%lld\n",ans); } ``` ]]> 0 /archives/90/#comments /feed/archives/90/ /archives/83/ /archives/83/ Sun, 27 Nov 2016 12:35:00 +0800 admin ###Description 给一个长为n的序列a，每个数在0到v - 1之间，有m次操作。 操作1：每次询问一个区间中是否可以选出两个下标的集合X，Y，满足： 1.X和Y没有交集 2.设集合X中有一个元素是i，则其对集合X的贡献是a[i] + 1，要求集合X的元素的总贡献和集合Y的元素的总贡献 相等如果可以选出这两个集合，输出 Yuno否则输出 Yuki 操作2：修改一个区间l,r之间的数，使得所有l <= i <= r，a[i] = a[i] \* a[i] \* a[i] % v ，即区间立方 ###Input 第一行三个数n , m , v，意义如题所述 之后一行n个数，表示序列a 之后m行每行三个数opt , l , r，表示操作类型是1还是2，操作的区间是[l , r] ###Output m行，每行一个字符串 Yuno 或者 Yuki 表示能否选出这两个集合 ###Sample Input 20 20 152 3 26 133 54 79 81 72 109 66 91 82 100 35 23 104 17 51 114 12 58 2 1 17 2 6 12 1 1 12 2 3 5 2 11 11 2 7 19 2 6 15 1 5 12 1 1 9 1 10 19 2 3 19 2 6 20 2 1 13 2 1 15 2 1 9 1 1 1 2 1 7 2 7 19 2 6 19 2 3 6 ###Sample Output Yuno Yuno Yuno Yuno Yuki ###HINT 总算在bzoj上出题了呀 这下可以安心退役了~ 总共有10组数据 对于100%的数据，n , m <= 100000 , v <= 1000,数据没有梯度 ###Solution 当某个区间长度大于13一定有解，小于13 bitset乱搞 立方操作树状数组区间加，取数时倍增 ###Code ```c++ #include<bits/stdc++.h> int n,m,v,u,s[100001],p[100001],N[1000][17],i,j,O,l,r,t,T; main() { scanf("%d%d%d",&n,&m,&v); while((1<<u)<=v)u++; for(;i<v;i++) N[i][0]=1ll*i*i*i%v; for(i=1;i<=n;i++) scanf("%d",s+i); for(i=0;i<16;i++) for(j=0;j<v;j++) N[j][i+1]=N[N[j][i]][i]; while(m--) { scanf("%d%d%d",&O,&l,&r); if(O&1) { if(r-l>=u)puts("Yuno"); else { std::bitset<10360> x(1); for(i=l;i<=r;i++) { t=0,T=s[i]; for(j=i;j;j^=j&-j)t+=p[j]; for(j=0;j<17;j++)if((t>>j)&1)T=N[T][j]; if((x&(x<<T+1)).any()) { puts("Yuno"); goto Y; } x|=x<<T+1; } puts("Yuki"); Y:; } } else { for(i=l;i<=n;i+=i&-i)p[i]++; for(i=r+1;i<=n;i+=i&-i)p[i]--; } } } ``` ]]> 0 /archives/83/#comments /feed/archives/83/ /archives/80/ /archives/80/ Thu, 17 Nov 2016 00:28:00 +0800 admin ###Description 您需要写一种数据结构（可参考题目标题），来维护一个有序数列，其中需要提供以下操作： 1.查询k在区间内的排名 2.查询区间内排名为k的值 3.修改某一位值上的数值 4.查询k在区间内的前驱(前驱定义为小于x，且最大的数) 5.查询k在区间内的后继(后继定义为大于x，且最小的数) ###Input 第一行两个数 n,m 表示长度为n的有序序列和m个操作 第二行有n个数，表示有序序列 下面有m行，opt表示操作标号 若opt=1 则为操作1，之后有三个数l,r,k 表示查询k在区间[l,r]的排名 若opt=2 则为操作2，之后有三个数l,r,k 表示查询区间[l,r]内排名为k的数 若opt=3 则为操作3，之后有两个数pos,k 表示将pos位置的数修改为k 若opt=4 则为操作4，之后有三个数l,r,k 表示查询区间[l,r]内k的前驱 若opt=5 则为操作5，之后有三个数l,r,k 表示查询区间[l,r]内k的后继 ###Output 对于操作1,2,4,5各输出一行，表示查询结果 ###Sample Input 9 6 4 2 2 1 9 4 0 1 1 2 1 4 3 3 4 10 2 1 4 3 1 2 5 9 4 3 9 5 5 2 8 5 ###Sample Output 2 4 3 4 9 ###HINT 1.n和m的数据范围：n,m<=50000 2.序列中每个数的数据范围：[0,1e8] 3.虽然原题没有，但事实上5操作的k可能为负数 ###Solution 外层树状数组，内层值域线段树，在每个节点记count,修改时分别修改，查询时用r和l-1对应的一大堆节点做差（有点像主席树） ###Code ```c++ #include<bits/stdc++.h> typedef unsigned char uchar; typedef unsigned int uint; typedef long long ll; typedef unsigned long long ull; typedef double db; typedef long double ldb; #define xx first #define yy second template<typename T> inline T max(T a,T b){return a>b?a:b;} template<typename T> inline T min(T a,T b){return a<b?a:b;} template<typename T> inline T abs(T a){return a>0?a:-a;} template<typename T> inline void repr(T &a,T b){if(a<b)a=b;} template<typename T> inline void repl(T &a,T b){if(a>b)a=b;} template<typename T> T gcd(T a,T b){if(b)return gcd(b,a%b);return a;} #define mp(a,b) std::make_pair(a,b) #define pb push_back #define lb(x) ((x)&(-(x))) #define sqr(x) ((x)*(x)) struct node { node *lc,*rc; int cnt; node(); }_null,*null=&_null; node::node(){lc=rc=null;cnt=0;} int pf; void erase(node *x) { if(x->lc!=null)erase(x->lc); if(x->rc!=null)erase(x->rc); delete x; } void modify(node *&x,int l,int r,int p,int v) { if(x==null)x=new node; x->cnt+=v; if(!x->cnt) { erase(x); x=null; return; } if(l!=r) { int f=(l+r)/2; if(p<=f) modify(x->lc,l,f,p,v); else modify(x->rc,f+1,r,p,v); } } struct group { node *x[50]; int mul[50],sz; inline int cnt() { int ret=0; for(int i=0;i<sz;i++)ret+=x[i]->cnt*mul[i]; return ret; } inline group* lc(group *f) { f->sz=sz; for(int i=0;i<sz;i++)f->x[i]=x[i]->lc,f->mul[i]=mul[i]; return f; } inline group* rc(group *f) { f->sz=sz; for(int i=0;i<sz;i++)f->x[i]=x[i]->rc,f->mul[i]=mul[i]; return f; } }; int cnt(group *x,int l,int r,int ql,int qr) { if(l==ql&&r==qr)return x->cnt(); int t=(l+r)/2,ans=0; group ch; if(ql<=t)ans+=cnt(x->lc(&ch),l,t,ql,min(t,qr)); if(qr>t)ans+=cnt(x->rc(&ch),t+1,r,max(ql,t+1),qr); return ans; } int kth(group *x,int l,int r,int rk) { if(l==r)return l; group ch; x->lc(&ch); int lcnt; if((lcnt=ch.cnt())>=rk) return kth(&ch,l,(l+r)/2,rk); else return kth(x->rc(&ch),(l+r)/2+1,r,rk-lcnt); } int gmax(group *x,int l,int r,int p) { if(!x->cnt())return 0; if(l==r)return l; int t=(l+r)/2; group ch; if(p<=t)return gmax(x->lc(&ch),l,t,p); if(r==p) { x->rc(&ch); if(ch.cnt())return gmax(&ch,t+1,r,p); return gmax(x->lc(&ch),l,t,t); } return max(gmax(x->lc(&ch),l,t,t),gmax(x->rc(&ch),t+1,r,p)); } int gmin(group *x,int l,int r,int p) { if(!x->cnt())return 0x7fffffff; if(l==r)return l; int t=(l+r)/2; group ch; if(p>t)return gmin(x->rc(&ch),t+1,r,p); if(l==p) { x->lc(&ch); if(ch.cnt())return gmin(&ch,l,t,p); return gmin(x->rc(&ch),t+1,r,t+1); } return min(gmin(x->lc(&ch),l,t,p),gmin(x->rc(&ch),t+1,r,t+1)); } #define nl 0 #define nr 100000001 node *root[50001]; int v[50001]; int main() { int n,m; scanf("%d%d",&n,&m); for(int i=0;i<=n;i++) root[i]=new node; for(int i=1;i<=n;i++) { scanf("%d",v+i); for(int j=i;j<=n;j+=lb(j)) modify(root[j],nl,nr,v[i],1); } while(m--) { int opt,a,b,c; scanf("%d%d%d",&opt,&a,&b); if(opt==3) { for(int j=a;j<=n;j+=lb(j)) modify(root[j],nl,nr,v[a],-1); v[a]=b; for(int j=a;j<=n;j+=lb(j)) modify(root[j],nl,nr,v[a],1); } else { scanf("%d",&c); group tmp; tmp.sz=0; for(int j=b;j;j^=lb(j)) tmp.mul[tmp.sz]=1,tmp.x[tmp.sz++]=root[j]; for(int j=a-1;j;j^=lb(j)) tmp.mul[tmp.sz]=-1,tmp.x[tmp.sz++]=root[j]; if(opt==1) { printf("%d\n",cnt(&tmp,nl,nr,nl,min(nr,c-1))+1); } else if(opt==2) { printf("%d\n",kth(&tmp,nl,nr,c)); } else if(opt==4) { printf("%d\n",gmax(&tmp,nl,nr,min(nr,c-1))); } else { printf("%d\n",gmin(&tmp,nl,nr,max(nl,c+1))); } } } } ``` ]]> 0 /archives/80/#comments /feed/archives/80/ /archives/72/ /archives/72/ Wed, 09 Nov 2016 16:51:00 +0800 admin ###Description 1946 年 3 月 5 日，英国前首相温斯顿·丘吉尔在美国富尔顿发表“铁幕演说”，正式拉开了冷战序幕。 美国和苏联同为世界上的“超级大国”，为了争夺世界霸权，两国及其盟国展开了数十年的斗争。在这段时期，虽然分歧和冲突严重，但双方都尽力避免世界范围的大规模战争（第三次世界大战）爆发，其对抗通常通过局部代理战争、科技和军备竞赛、太空竞争、外交竞争等“冷”方式进行，即“相互遏制，不动武力”，因此称之为“冷战”。 Reddington 是美国的海军上将。由于战争局势十分紧张，因此他需要时刻关注着苏联的各个活动，避免使自己的国家陷入困境。苏联在全球拥有 N 个军工厂，但由于规划不当，一开始这些军工厂之间是不存在铁路的，为了使武器制造更快，苏联决定修建若干条道路使得某些军工厂联通。 Reddington 得到了苏联的修建日程表，并且他需要时刻关注着某两个军工厂是否联通，以及最早在修建哪条道路时会联通。具体而言，现在总共有M 个操作，操作分为两类： • 0 u v，这次操作苏联会修建一条连接 u 号军工厂及 v 号军工厂的铁路，注意铁路都是双向的; • 1 u v， Reddington 需要知道 u 号军工厂及 v 号军工厂最早在加入第几条条铁路后会联通，假如到这次操作都没有联通，则输出 0; 作为美国最强科学家， Reddington 需要你帮忙设计一个程序，能满足 他的要求。 ###Input 第一行两个整数 N, M。 接下来 M 行，每行为 0 u v 或 1 u v 的形式。 数据是经过加密的，对于每次加边或询问，真正的 u, v 都等于读入的 u, v 异或上上一次询问的答案。一开始这个值为 0。 1 ≤ N, M ≤ 500000，解密后的 u, v 满足1 ≤ u, v ≤ N, u不等于v ###Output 对于每次 1 操作，输出 u, v 最早在加入哪条边后会联通，若到这个操 作时还没联通，则输出 0。 ###Sample Input 5 9 0 1 4 1 2 5 0 2 4 0 3 4 1 3 1 0 7 0 0 6 1 0 1 6 1 2 6 ###Sample Output ``` 0 3 5 ``` ###Solution 直接用LCT维护动态最小生成树就行了，虽然很暴力，但能AC ###Code ```c++ #include<bits/stdc++.h> typedef unsigned char uchar; typedef unsigned int uint; typedef long long ll; typedef unsigned long long ull; typedef long double ldb; #define xx first #define yy second template<typename T> inline T max(T a,T b){return a>b?a:b;} template<typename T> inline T min(T a,T b){return a<b?a:b;} template<typename T> inline T abs(T a){return a>0?a:-a;} template<typename T> inline void repr(T &a,T b){if(a<b)a=b;} template<typename T> inline void repl(T &a,T b){if(a>b)a=b;} template<typename T> inline T gcd(T a,T b){if(b)return gcd(b,a%b);return a;} #define mp(a,b) std::make_pair(a,b) #define pb push_back #define lb(x) ((x)&(-(x))) #define pm(a,b,c,d) a=(a+(ll)(b)*(c))%(d) const int N=1000001; struct node { node *c[2],*fa; int val,ma; bool rev; inline void rotate(bool f); inline void pushdown(); inline void pushup(); }s[N],_null,*null=&_null; inline void node::pushdown() { if(fa->c[0]==this||fa->c[1]==this) fa->pushdown(); if(rev) { rev=0; std::swap(c[0],c[1]); if(c[0]!=null)c[0]->rev=!c[0]->rev; if(c[1]!=null)c[1]->rev=!c[1]->rev; } } inline void node::rotate(bool f) { fa->c[f]=c[!f]; c[!f]=fa; fa=c[!f]->fa; if(c[!f]->fa->c[1]==c[!f]) c[!f]->fa->c[1]=this; else if(c[!f]->fa->c[0]==c[!f]) c[!f]->fa->c[0]=this; c[!f]->fa=this; c[!f]->c[f]->fa=c[!f]; c[!f]->pushup(); } inline void node::pushup() { ma=val; if(c[0]!=null)repr(ma,c[0]->ma); if(c[1]!=null)repr(ma,c[1]->ma); } inline void init(node *x,int v) { x->val=v,x->c[0]=null,x->c[1]=null,x->fa=null; } inline void splay(node *a) { a->pushdown(); while(a->fa->c[0]==a||a->fa->c[1]==a) a->rotate(a==a->fa->c[1]); a->pushup(); } inline void access(node *a) { node *x=null; while(a!=null) { splay(a); a->c[1]=x; a->pushup(); x=a,a=a->fa; } } inline void movetoroot(node *x) { access(x); splay(x); x->rev=!x->rev; } inline void link(node *x,node *y) { movetoroot(x); x->fa=y; } inline void cut(node *x,node *y) { movetoroot(x); access(y); splay(y); x->fa=null; y->c[0]=null; y->pushup(); } inline void split(node *x,node *y) { movetoroot(x),access(y),splay(y); } inline node* findroot(node *x) { while(x->fa!=null) x=x->fa; return x; } int main() { int n,m,lstans=0,opt,x,y; scanf("%d%d",&n,&m); for(int i=1;i<=n;i++) init(s+i,0); for(int i=1,ec=0;i<=m;i++) { scanf("%d%d%d",&opt,&x,&y); x^=lstans,y^=lstans; if(opt==0) { ec++; if(findroot(s+x)!=findroot(s+y)) { init(s+n+ec,ec); link(s+x,s+n+ec); link(s+y,s+n+ec); } } else { split(s+x,s+y); if(findroot(s+x)==s+y) lstans=s[y].ma; else lstans=0; printf("%d\n",lstans); } } } ``` ]]> 1 /archives/72/#comments /feed/archives/72/ /archives/70/ /archives/70/ Wed, 09 Nov 2016 12:55:00 +0800 admin ###Description XLk觉得《上帝造题的七分钟》不太过瘾，于是有了第二部。 "第一分钟，X说，要有数列，于是便给定了一个正整数数列。 第二分钟，L说，要能修改，于是便有了对一段数中每个数都开平方(下取整)的操作。 第三分钟，k说，要能查询，于是便有了求一段数的和的操作。 第四分钟，彩虹喵说，要是noip难度，于是便有了数据范围。 第五分钟，诗人说，要有韵律，于是便有了时间限制和内存限制。 第六分钟，和雪说，要省点事，于是便有了保证运算过程中及最终结果均不超过64位有符号整数类型的表示范围的限制。 第七分钟，这道题终于造完了，然而，造题的神牛们再也不想写这道题的程序了。" ——《上帝造题的七分钟·第二部》 所以这个神圣的任务就交给你了。 ###Input 第一行一个整数n，代表数列中数的个数。 第二行n个正整数，表示初始状态下数列中的数。 第三行一个整数m，表示有m次操作。 接下来m行每行三个整数k,l,r，k=0表示给[l,r]中的每个数开平方(下取整)，k=1表示询问[l,r]中各个数的和。 ###Output 对于询问操作，每行输出一个回答。 ###Sample Input 10 1 2 3 4 5 6 7 8 9 10 5 0 1 10 1 1 10 1 1 5 0 5 8 1 4 8 ###Sample Output 19 7 6 ###Solution 显然，一个数最多开根6次就会变成1 那么直接用线段树维护区间最大值，每次暴力修改即可 ###Code ```c++ #include<bits/stdc++.h> typedef unsigned char uchar; typedef unsigned int uint; typedef long long ll; typedef unsigned long long ull; #define xx first #define yy second template<typename T> inline T max(T a,T b){return a>b?a:b;} template<typename T> inline T min(T a,T b){return a<b?a:b;} template<typename T> inline T abs(T a){return a>0?a:-a;} template<typename T> inline void repr(T &a,T b){if(a<b)a=b;} template<typename T> inline void repl(T &a,T b){if(a>b)a=b;} #define mp(a,b) std::make_pair(a,b) #define pb push_back int n,t=1; ll s[270000],ma[270000]; inline void up(int x) { s[x]=s[x<<1]+s[x<<1|1]; ma[x]=max(ma[x<<1],ma[x<<1|1]); } void modify(int x,int l,int r,int ql,int qr) { if(ma[x]<=1)return; if(x&t) { ma[x]=sqrt(ma[x]); s[x]=ma[x]; return; } int q=(l+r)>>1; if(ql<q)modify(x<<1,l,q,ql,min(q,qr)); if(qr>q)modify(x<<1|1,q,r,max(q,ql),qr); up(x); } int main() { int m; scanf("%d",&n); while(t<n+2)t<<=1; for(int i=1;i<=n;i++) scanf("%lld",ma+i+t),s[i+t]=ma[i+t]; for(int i=t-1;i;i--) up(i); scanf("%d",&m); while(m--) { int opt,x,y; scanf("%d%d%d",&opt,&x,&y); if(x>y)std::swap(x,y); if(opt==0) { modify(1,1,t,x,y+1); } else { x=x+t-1,y=y+t+1; ll ans=0; while(x^y^1) { if(~x&1)ans+=s[x^1]; if(y&1)ans+=s[y^1]; x>>=1,y>>=1; } printf("%lld\n",ans); } } } ``` ]]> 0 /archives/70/#comments /feed/archives/70/