51nod filling in holes (3)(1203,1695)

Chong Wang Lv6
  2018-12-09 01:11:51 2018-12-09 01:11:51 Created   2026-10-09 09:07:16 2026-10-09 09:07:16 Updated  

It’s actually over one o’clock now. . . If you don’t summarize the question, you haven’t done it.

51nod 1203

Through this question, I reviewed Captain Mo again, but I had forgotten many of them.

For prime numbers <230, you can use RMQ, and you will find that there are only 50.

The discovery of prime numbers > 230 is only possible with 0 or 1, Team Mo.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
int num[maxn];
struct RMQ {
    int f_min[maxn][20],f_max[maxn][20];
     
    void init(int n)
    {
        for(int i = 1; i <= n; i++)
        {
            f_min[i][0] = f_max[i][0] = num[i];
        }

    
        for(int i = 1; (1<<i) <= n; i++)  // Transition in increasing interval-length order.
        {
            for(int j = 1; j+(1<<i)-1 <= n; j++)  // Interval starting position.
            {
                f_max[j][i] = max(f_max[j][i-1],f_max[j+(1<<(i-1))][i-1]);
                f_min[j][i] = min(f_min[j][i-1],f_min[j+(1<<(i-1))][i-1]);
            }
        }
    
    }
     
    int query_max(int l,int r)
    {
        int k = (int)(log(double(r-l+1))/log((double)2));
        return max(f_max[l][k], f_max[r-(1<<k)+1][k]);
    }
     
    int query_min(int l,int r)
    {
        int k = (int)(log(double(r-l+1))/log((double)2));
        return min(f_min[l][k], f_min[r-(1<<k)+1][k]);
    }
}rmq;

ll vis[maxn];
vector<int>v;
map<int,int>ind;
map<int,int>an_ind;
ll val[maxn],ni[maxn];

struct Q{
    int le;
    int ri;
    int id;
}q[maxn];

ll ans[maxn];
int pos[maxn];
bool cmp(Q & a, Q & b) {
    return pos[a.le]<pos[b.le] || (pos[a.le]==pos[b.le] && a.ri<b.ri); 
}
int last[maxn];
int v_le[maxn],v_ri[maxn];
vector<int>pri;
void solve() {
    int up = 230;
    int cnt = 0;
    repp(i,2,up) {
        if(vis[i])continue;
        pri.push_back(i);
        for(int j=i;j<=up;j+=i) {
            vis[j]=1;
        }
    }

    int n;
    int h;
    sa(n);    
    sa(h);
    repp(i,1,n){
        int x;
        sa(x);
        vis[i]=x;
    }
    repp(i,1,h) {
        sa(q[i].le);
        sa(q[i].ri);
        q[i].id=i;
        ans[i]=1;
    }
    rep(i,0,pri.size()) {
        memset(num,0,sizeof(num));
        repp(k,1,n) {
            int g = vis[k];
            while(g%pri[i]==0) {
                num[k]++;
                g/=pri[i];
            }
            vis[k]=g;
        }

        rmq.init(n);
        
        repp(j,1,h) {
            int le = q[j].le;
            int ri = q[j].ri;
            int id = q[j].id;
            ll d = rmq.query_max(le,ri);
            ans[id] = ans[id]*po(pri[i],d,mod)%mod;
        } 
    }
    repp(i,1,n) {
        val[i]=vis[i];
    }
    int bk = ceil(sqrt(1.0*n));
    for (int i = 1; i <= n; i++)
    {
        pos[i] = (i - 1) / bk + 1;
    }
    memset(last,0,sizeof(last));
    repp(i,1,n) {
        v_le[i]=last[val[i]];
        last[val[i]]=i;
    }
    memset(last,0,sizeof(last));
    for(int i=n;i>=1;i--) {
        if(last[val[i]]==0) {
            last[val[i]]=n+1;
        }
        v_ri[i]=last[val[i]];
        last[val[i]]=i;
    }
    int pl = 1; 
    int pr = 0;
    int j;
    val[0]=val[n+1]=0;
    sort(q+1,q+h+1,cmp);
    repp(i,1,n) {
        ni[i] = po(val[i],mod-2,mod);
    }
    ll cur = 1;
    for (int i = 1; i <= h; i++)
    {
        while(pl<q[i].le) {
            if(v_ri[pl]>pr) {
                cur = cur%mod*ni[pl]%mod;
            }
            pl++;
        }
        while(pl>q[i].le) {
            pl--;
            if(v_ri[pl]>pr) {
                cur = cur%mod*val[pl]%mod;
            }
        }
        while(pr>q[i].ri) {
            if(v_le[pr]<pl) {
                cur = cur%mod*ni[pr]%mod;
            }
            pr--;
        }
        while(pr<q[i].ri) {
            pr++;
            if(v_le[pr]<pl) {
                cur = cur%mod*val[pr]%mod;
            }
        }
        ans[q[i].id]=ans[q[i].id]*cur%mod;
    }

    repp(i,1,h){
        ll x;
        printf("%lld\n",ans[i]);
    }

}

51nod 1695

Dreamoon’s question was asked a long time ago.

The meaning of the question is that given a tree, each edge on the tree has a corresponding weight. Each point has a maximum value $R_x$ to other points. Given a len, find a point set where the maximum difference between $R_x$ is less than len. Find the maximum value of this point set.

Not at all, after thinking about it for a long time, not at all. . .

First, consider finding $R_x$ for each point, which is the maximum value of the two points from each point to the diameter of the tree. This is no problem, it is within the scope of meeting. . .

How to find this maximum point set? It’s impossible. . . . . . . . . .

It turns out that I am looking for the root of the tree, recorded as r, and I found that $R_x - R_r < len$ is OK. I thought so. . .

Then came the method of checking scores on trees. It was my first time to think about it and it was very clever.

Go up from this node to the unreachable node -1, and get +1 here. Each time, points that meet the conditions within its own subtree are added.

Wow, this is a great question. . . .

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
int n;
ll dis[maxn], v[maxn];
vector< pair<int, int> > edge[maxn];

void dfs1(int x, int fa, int d)
{
    if(fa==-1){
        dis[x]=0;
    } else {
        dis[x] = dis[fa] + d;
    }
    for(int i=0;i<edge[x].size();i++) {
        int nxt = edge[x][i].first;
        if(nxt == fa) {
            continue;
        }
        dfs1(nxt,x,edge[x][i].second);
    }
}
int root=1;
ll v2[maxn][2];
void findroot()
{
    memset(dis,0,sizeof(dis));
    dfs1(1, -1, 0);
    int x = 1;
    repp(i,1,n) {
        if(dis[i] > dis[x]) {
            x=i;
        }
    }

    memset(dis,0,sizeof(dis));
    dfs1(x,-1,0);
    int y=1;
    repp(i,1,n) {
        if(dis[i]>dis[y]){
            y=i;
        }
        v2[i][0]=dis[i];
    }

    memset(dis,0,sizeof(dis));
    dfs1(y,-1,0);
    repp(i,1,n) {
        v2[i][1]=dis[i];
    }

    repp(i,1,n) {
        v[i] = max(v2[i][0],v2[i][1]);
    }
    root=1;
    repp(i,1,n) {
        if(v[i]<v[root]) {
            root=i;
        }
    }
    repp(i,1,n) {
        dis[i]=max(v2[i][0],v2[i][1]);
    }
}

int cnt = 0;
int le[maxn],ri[maxn],sum[maxn];
int anc[maxn][20];

void dfsroot(int x,int fa) {
    ++cnt;
    le[x] = cnt;
    anc[x][0] = fa;
    repp(i,1,18){
        if(anc[x][i-1]==-1) {
            anc[x][i]=-1;
            continue;
        }
        anc[x][i] = anc[anc[x][i-1]][i-1];
    }
    for(int i=0;i<edge[x].size();i++) {
        int nxt = edge[x][i].first;
        if(nxt==fa) {
            continue;
        }
        dfsroot(nxt,x);
    }
    ri[x] = cnt;
}

void solve()
{
    sa(n);
    repp(i, 1, n - 1)
    {
        int x, y, z;
        sa(x), sa(y), sa(z);
        edge[x].push_back(mp(y, z));
        edge[y].push_back(mp(x, z));
    }
    findroot();

    dfsroot(root,-1);
    int q;
    sa(q);
    repp(i,1,q) {
        ll len;
        slla(len);

        memset(sum,0,sizeof(sum));
        repp(i,1,n){
            if(dis[i]-dis[root]<=len) {
                sum[le[i]]++;
                continue;
            }
            int y=i;
            for(int k=18;k>=0;k--) {
                if(y==-1) {
                    break;
                }
                if(dis[i]-dis[anc[y][k]]<=len) {
                    y=anc[y][k];
                }
            }
            if(y!=-1)
                y=anc[y][0];
            if(y!=-1)
                sum[le[y]]--;
            sum[le[i]]++;
        }
        repp(i,1,n){
            sum[i] += sum[i-1];
        }
        int ans = 0;
        repp(i,1,n){
            ans = max(ans, sum[ri[i]] - sum[le[i]-1]);
        }
        printf("%d\n", ans);
    }
}

On this page
51nod filling in holes (3)(1203,1695)
  1. 51nod 1203
  2. 51nod 1695