When I was awake, I took rank 1 in a confused way. Probably because I got to the original question, it seems that OI still needs to ask questions about sea tactics (o ^ o).
Gapari's party
256MB / 1s ; japari.cpp / c / pas / in / out
[Title Description]
There are n areas in Gapari Park, and n-1 roads connect them together to form a tree structure. At first, there are Ai friends in the first region, but because of the role of Sandstar, sometimes the number of friends in all regions on the simple path from region x to region y will increase v, and sometimes the number of friends in all regions on the simple path from region x to region y will become v.
Sometimes friends in all areas of the simple path from area x to area y want to get together, and they need to select a part of the friends from all the parties as staff. Gapari's friends like prime numbers, so they want the number of staff and non-staff participants to be prime numbers.
Please tell them if there is a plan for each party to meet their needs.
[Input Format]
The first line has two integers n,m, representing the number of friends and the number of events.
The next line contains n numbers, and the number i represents Ai.
The next n-1 line, with two numbers x and Y in each line, indicates that there is an undirected path between X and y.
Next in line m, the first integer opt in each line represents the event type.
If opt=1, the next three integers, x,y,v, indicate that the number of friends in all regions on a simple path from the X region to the Y region increases by V.
If opt=2, the next three integers, x,y,v, denote that the number of friends for all regions on a simple path from the X region to the Y region becomes v.
If opt=3, the next two integers, x and y, represent the friends of all regions on a simple path from the x region to the Y region.
[Output Format]
For each three events, if the number of staffs and non-staffs can be prime, output a line of SUGOI, otherwise output a line of TANOSHI.
[Sample data]
japari1.in
3 4
1 2 1
2 1
3 2
2 2 1 4
1 3 3 -1
2 2 2 2
3 1 3
japari1.out
SUGOI
japari2.in
4 6
2 4 0 0
2 1
3 2
4 3
2 1 4 2
1 4 4 9
1 3 2 -2
2 4 2 5
3 1 4
3 4 4
japari2.out
TANOSHI
SUGOI
[Example Interpretation]
In the first example, the number of friends in the three regions is 4, 2, 0, and the number of friends and 6, respectively. They can be divided into two groups. The number of friends in each group is 3.
In the second example, the number of friends in the four regions is 2, 5, 5, and 5 in turn, and the number of friends and S in the first query is 17, which can not be divided into two groups. The friends and S of the second question are 5, which can be divided into two groups. The number of friends in each group is 2 and 3, respectively.
[Data Scope]
For 30% of the data, n,m < 5000.
For the other 30% of the data, for I > 1, the first region is directly connected with the i-1 region.
For 100% of the data, 1 < n,m < 100000, 1 < x,y < n always meet 0 < Ai,S < 10000000. In increasing events, v may be negative.
Solution: Naked tree chain partition, pay attention to the line segment tree two kinds of conflicting markers download order. Although it's a troublesome problem, it really solidifies the foundation.
P.S. It is suggested that the initial values of the tags be assigned to -INF.
#include<cstdio>
#include<cstring>
#include<iostream>
#include<algorithm>
using namespace std;
#define root 1,1,n
#define lson rt<<1,l,mid
#define rson rt<<1|1,mid+1,r
const int MAX=1e7+4,MAXN=1e5+4,INF=0x3f3f3f3f;
bool vis[MAX],ok[MAX];
int n,m,prime[MAX/10],tot=0;
int top[MAXN],dep[MAXN],fa[MAXN],son[MAXN],siz[MAXN],head[MAXN],edge=0;
int tid[MAXN],rk[MAXN],num[MAXN],tim=0;
struct EDGE {
int v,nxt;
}e[MAXN<<1];
inline void adde(int u,int v) {
e[edge].nxt=head[u],e[edge].v=v,head[u]=edge++;
e[edge].nxt=head[v],e[edge].v=u,head[v]=edge++;
}
/*------------pre_process------------*/
inline void linear_shaker() {
memset(ok,false,sizeof(ok));
memset(vis,false,sizeof(vis));
for (register int i=2;i<MAX;++i) {
if (!vis[i]) prime[++tot]=i;
for (int j=1;j<=tot&&i*prime[j]<MAX;++j) {
vis[i*prime[j]]=true;
if (i%prime[j]==0) break;
}
}
for (int i=4;i<MAX;i+=2) ok[i]=true;
for (int i=1;i<=tot;++i) ok[prime[i]+2]=true;
}
/*------------DCP------------*/
inline void dfs1(int p,int father,int d) {
dep[p]=d,fa[p]=father,siz[p]=1;
for (int i=head[p];~i;i=e[i].nxt) {
int v=e[i].v;
if (v==father) continue;
dfs1(v,p,d+1);
siz[p]+=siz[v];
if (son[p]==-1||siz[v]>siz[son[p]])
son[p]=v;
}
}
inline void dfs2(int p,int tp) {
top[p]=tp,tid[p]=++tim,rk[tid[p]]=p;
if (son[p]==-1) return ;
dfs2(son[p],tp);
for (int i=head[p];~i;i=e[i].nxt) {
int v=e[i].v;
if (v!=fa[p]&&v!=son[p])
dfs2(v,v);
}
}
/*------------Segment Tree------------*/
int sum[MAXN<<2],set[MAXN<<2],laz[MAXN<<2];//add/change
inline void pushup(int rt) {
sum[rt]=sum[rt<<1]+sum[rt<<1|1];
}
inline void pushdown(int rt,int len) {
if (set[rt]!=-INF) {
sum[rt<<1]=set[rt]*(len-(len>>1));
sum[rt<<1|1]=set[rt]*(len>>1);
set[rt<<1]=set[rt<<1|1]=set[rt];
laz[rt<<1]=laz[rt<<1|1]=0;
set[rt]=-INF;
}
if (laz[rt]!=-INF) {
sum[rt<<1]+=laz[rt]*(len-(len>>1));
sum[rt<<1|1]+=laz[rt]*(len>>1);
if (laz[rt<<1]!=-INF) laz[rt<<1]+=laz[rt];
else laz[rt<<1]=laz[rt];
if (laz[rt<<1|1]!=-INF) laz[rt<<1|1]+=laz[rt];
else laz[rt<<1|1]=laz[rt];
laz[rt]=-INF;
}
}
void build(int rt,int l,int r) {
set[rt]=-INF,laz[rt]=-INF;
if (l==r) {sum[rt]=num[rk[l]];return ;}
int mid=(l+r)>>1;
build(lson),build(rson);
pushup(rt);
}
void add(int rt,int l,int r,int L,int R,int val) {
if (L<=l&&r<=R) {
sum[rt]+=val*(r-l+1);
if (laz[rt]==-INF) laz[rt]=val;
else laz[rt]+=val;
return ;
}
pushdown(rt,r-l+1);
int mid=(l+r)>>1;
if (L<=mid) add(lson,L,R,val);
if (mid<R) add(rson,L,R,val);
pushup(rt);
}
void change(int rt,int l,int r,int L,int R,int val) {
if (L<=l&&r<=R) {
sum[rt]=val*(r-l+1);
laz[rt]=-INF,set[rt]=val;
return ;
}
pushdown(rt,r-l+1);
int mid=(l+r)>>1;
if (L<=mid) change(lson,L,R,val);
if (mid<R) change(rson,L,R,val);
pushup(rt);
}
int query(int rt,int l,int r,int L,int R) {
if (L<=l&&r<=R) return sum[rt];
pushdown(rt,r-l+1);
int mid=(l+r)>>1,res=0;
if (L<=mid) res+=query(lson,L,R);
if (mid<R) res+=query(rson,L,R);
return res;
}
void modify(int x,int y,int val,int type) {
while (top[x]!=top[y]) {
if (dep[top[x]]<dep[top[y]]) x^=y^=x^=y;
if (type==1) add(root,tid[top[x]],tid[x],val);
else change(root,tid[top[x]],tid[x],val);
x=fa[top[x]];
}
if (dep[x]<dep[y]) x^=y^=x^=y;
if (type==1) add(root,tid[y],tid[x],val);
else change(root,tid[y],tid[x],val);
}
int ask(int x,int y) {
int res=0;
while (top[x]!=top[y]) {
if (dep[top[x]]<dep[top[y]]) x^=y^=x^=y;
res+=query(root,tid[top[x]],tid[x]);
x=fa[top[x]];
}
if (dep[x]<dep[y]) x^=y^=x^=y;
res+=query(root,tid[y],tid[x]);
// printf("%d\n",res);
return res;
}
inline int read() {
int x=0,f=1;char c=getchar();
while (c<'0'||c>'9') {if (c=='-') f=-1;c=getchar();}
while (c>='0'&&c<='9') x=x*10+c-'0',c=getchar();
return x*f;
}
int main() {
freopen("japari.in","r",stdin);
freopen("japari.out","w",stdout);
// printf("memory==%d\n",sizeof(prime)+sizeof(ok)<<1);
linear_shaker();
memset(head,-1,sizeof(head));
memset(son,-1,sizeof(son));
n=read(),m=read();
for (register int i=1;i<=n;++i) num[i]=read();
for (register int i=1;i<n;++i) {
int u=read(),v=read();
adde(u,v);
}
dfs1(1,0,0);
dfs2(1,1);
build(root);
for (register int cv=0;cv<m;++cv) {
int type=read();
switch (type) {
case 1:{
int x=read(),y=read(),v=read();
modify(x,y,v,1);
break;
}
case 2:{
int x=read(),y=read(),v=read();
modify(x,y,v,2);
break;
}
case 3:{
int x=read(),y=read();
int ans=ask(x,y);
puts(ok[ans]?"SUGOI":"TANOSHI");
break;
}
}
}
return 0;
}Black and White Bear Code
256MB / 1s ; monokuma.cpp / c / pas / in / out
[Title Description]
Miao Mucheng has found an escape device that can help everyone escape from the Peak of Hope School. But to use it, you must enter a decimal n-digit password (no leading 0). In order to make the game more interesting, black and white bears provide m pieces of information, of which the information in section i indicates that the number of Li to Ri and Li to RI is exactly the same.
Miaomucheng decides to randomly select an n-digit input that meets the requirements. Please tell him the probability that he will touch the password.
[Input Format]
The first row contains two integers, N and m, representing the number of digits and the number of information provided by black and white bears.
Next m lines, each line has four positive integers Li,Ri,li,ri.
[Output Format]
Output a row of integers, indicating the probability of Nursery Trees colliding with the password, 998244353 modelling.
[Sample data]
monokuma.in
4 2
1 2 3 4
3 3 3 3
monokuma.out
144190851
[Example Interpretation]
The answer is 1/90 in the sense of module 998244353.
[Data Scope]
For 30% of the data, n,m < 2000.
For 100% data, 1 < n,m < 100000, 1 < Li < Ri < n, 1 < Li < RI < n, and guarantee Ri-Li=ri-li.
Question: See my blog, bzoj4569. Probably, every pair of intervals should be doubled to optimize the merge n times to merge logn times, and then merge all the intervals once. Finally, the answer is counted and the inverse element is found.
#include<cstdio>
#include<cstring>
#include<iostream>
#include<algorithm>
using namespace std;
typedef long long ll;
const int MAXN=1e5+2,MOD=998244353;
int n,m;
int fa[MAXN*20],id[MAXN][20],mk[MAXN*20][2],pw[20],tot=0,cnt=0,ans;
int find(int x) {
return fa[x]?fa[x]=find(fa[x]):x;
}
int merge(int x,int y) {
x=find(x);
y=find(y);
if (x!=y) fa[y]=x;
}
inline int read() {
int x=0;char c=getchar();
while (c<'0'||c>'9') c=getchar();
while (c>='0'&&c<='9') x=x*10+c-'0',c=getchar();
return x;
}
int fpow(int a,int b,int p) {
int ret=1;
while (b) {
if (b&1) ret=(ll)ret*a%p;
b>>=1,a=(ll)a*a%p;
}
return ret;
}
int main() {
freopen("monokuma.in","r",stdin);
freopen("monokuma.out","w",stdout);
memset(fa,0,sizeof(fa));
pw[0]=1;for (int i=1;i<=17;++i) pw[i]=pw[i-1]*2;
n=read(),m=read();
if (n==1) ans=10;
else {
for (register int i=1;i<=n;++i)
for (int j=0;j<=17;++j)
id[i][j]=++tot,mk[tot][0]=i,mk[tot][1]=j;
for (int i=1;i<=m;++i) {
int l1=read(),r1=read(),l2=read(),r2=read();
for (int j=17;j>=0;--j)
if (l1+pw[j]-1<=r1) {
merge(id[l1][j],id[l2][j]);
l1+=pw[j];l2+=pw[j];
}
}
for (int j=17;j>0;--j)
for (register int i=1;i<=n;++i) {
int k=find(id[i][j]);
int s=mk[k][0];
merge(id[s][j-1],id[i][j-1]);
merge(id[s+pw[j-1]][j-1],id[i+pw[j-1]][j-1]);
}
for (register int i=1;i<=n;++i)
if (!fa[id[i][0]]) ++cnt;
ans=9;
for (register int i=1;i<cnt;++i) ans=(ll)ans*10%MOD;
}
printf("%d\n",fpow(ans,MOD-2,MOD));
return 0;
}First Sound Tour in the Future
128MB / 1s ; cruise.cpp / c / pas / in / out
[Title Description]
Miku decided to take a tour of some of the n sites. These n locations are connected by n-1 roads, and there is only one path between them that can reach each other. Miku hopes to choose some of these roads with onions, so that Miku can choose a way to go only through the onion roads and tour all the places she chooses (a road can be passed many times, starting point is optional).
Miku wanted to know how many onions she needed to prepare at least. Since her itinerary plan may change, she hopes you can answer her questions as soon as you change it.
[Input Format]
The first line has two integers n,m, representing the number of locations and events.
Lines 2 to n, with two integers x and Y in each row, indicate that there is an undirected road between location x and location y.
The next line contains n 0/1 numbers. If the number of i is 1, it means that the location of i was selected initially, and 0 means that it is not selected.
The next line contains m integers, representing modification events in turn. The number i, Ai, indicates a change in the status of Ai's location, i.e. if it is currently selected, it will be changed to non-selected, and if it is not currently selected, it will be changed to selected.
[Output Format]
Output line m, line i an integer indicating the minimum amount of onions required for the first tone after the first event.
[Sample data]
cruise.in
5 8
1 2
1 3
2 4
2 5
1 0 0 1 0
5 4 2 1 2 5 3 2
cruise.out
3
2
2
1
0
0
0
2
[Data Scope]
For 30% of the data, n,m < 3000.
For another 30% of the data, all locations are not selected at the beginning, ensuring that the location of the modification operation is currently not selected.
For 100% data, 1 < n,m < 200000, 1 < x,y,Ai < n.
Problem Solution: It can be proved that the answer is twice as long as the distance between two adjacent selection points on the tree and the distance on the tree with the beginning and end points sorted by DFS. Pre-processing LCA, using set to maintain the selected points, and update the answers according to the precursor and successor points of DFS sequence. You can refer to bzoj3991, almost the same.
#include<cstdio>
#include<cstring>
#include<iostream>
#include<algorithm>
#include<set>
using namespace std;
const int MAXN=200005;
int n,m;
int head[MAXN],edge=0,ans=0,root;
struct EDGE {
int v,nxt;
}e[MAXN<<1];
int tid[MAXN],rk[MAXN],dep[MAXN],tim=0,f[20][MAXN];
int has[MAXN];
inline int read() {
int x=0,f=1;char c=getchar();
while (c<'0'||c>'9') {if (c=='-') f=-1;c=getchar();}
while (c>='0'&&c<='9') x=x*10+c-'0',c=getchar();
return x*f;
}
inline void adde(int u,int v) {
e[edge].nxt=head[u],e[edge].v=v,head[u]=edge++;
e[edge].nxt=head[v],e[edge].v=u,head[v]=edge++;
}
void dfs(int p,int fa) {
tid[p]=++tim,rk[tim]=p;
for (int i=head[p];~i;i=e[i].nxt) {
int v=e[i].v;
if (v^fa)
f[0][v]=p,dep[v]=dep[p]+1,dfs(v,p);
}
}
inline void da() {
for (int j=1;(1<<j)<=n;++j)
for (int i=1;i<=n;++i)
f[j][i]=f[j-1][f[j-1][i]];
}
inline int lca(int x,int y) {
if (dep[x]<dep[y]) x^=y^=x^=y;
int t=dep[x]-dep[y];
for (int i=0;i<=18;++i)
if (t&(1<<i)) x=f[i][x];
if (x==y) return x;
for (int i=18;~i;--i)
if (f[i][x]^f[i][y]) x=f[i][x],y=f[i][y];
return f[0][x];
}
inline int dis(int x,int y) {
// printf("%d %d %d\n",x,y,lca(x,y));
return dep[x]+dep[y]-(dep[lca(x,y)]<<1);
}
set<int> s;
set<int>::iterator it;
inline int ne(int x) {
it=s.find(tid[x]);
return ++it==s.end()?0:rk[*it];
}
inline int pr(int x) {
it=s.find(tid[x]);
return it==s.begin()?0:rk[*--it];
}
inline void add(int x) {
s.insert(tid[x]);
int l=pr(x),r=ne(x);
if (l) ans+=dis(l,x);
if (r) ans+=dis(r,x);
if (l&&r) ans-=dis(l,r);
}
inline void del(int x) {
int l=pr(x),r=ne(x);
if (l) ans-=dis(l,x);
if (r) ans-=dis(r,x);
if (l&&r) ans+=dis(l,r);
s.erase(tid[x]);
}
int main() {
freopen("cruise.in","r",stdin);
freopen("cruise.out","w",stdout);
memset(has,false,sizeof(has));
memset(head,-1,sizeof(head));
n=read(),m=read();
for (register int i=1;i<n;++i) {
int u=read(),v=read();
adde(u,v);
}
dep[1]=0;
dfs(1,0);
da();
for (register int i=1;i<=n;++i) {
int x=read();
if (x) add(i),has[i]=1;
}
while (m--) {
int x=read();
if (has[x]) del(x);
else add(x);
has[x]^=1;
printf("%d\n",s.size()?(ans+dis(rk[*s.begin()],rk[*--s.end()]))>>1:0);
// cout<<"size=="<<s.size()<<endl;
}
return 0;
}