#include <bits/stdc++.h>
using namespace std;
#define TL ios::sync_with_stdio(0),cin.tie(0),cout.tie(0);
#define rall(s) s.rbegin(),s.rend()
#define all(s) s.begin(),s.end()
#define pb push_back
#define se second
#define fi first
#define ll long long
#define ld long double
#define YES cout<<"YES\n"
#define Yes cout<<"Yes\n"
#define yes cout<<"yes\n"
#define NO cout<<"NO\n"
#define No cout<<"No\n"
#define no cout<<"no\n"
const int N = 5e5 + 9 , mod = 1e9 + 7;
ll a[N] , b[N] , dp[N] ,p[N] , sz[N] , c[N] , d[N] , ans[N] , t[N];
vector<pair<int,int>>v[N];
ll get(int x){
return (p[x] == x ? x : get(p[x]));
}
void join(int x , int y){
x = get(x) , y = get(y);
if(x != y){
if(sz[x] < sz[y])
swap(x , y);
p[y] = x;
sz[x] += sz[y];
}
}
bool bmp(int i , int j){
return c[i] > c[j];
}
struct query{
ll x , y , k;
}Q[N];
bool bmp1(query &i , query &j){
return i.y > j.y;
}
void pushup(int i){
t[i] = min(t[2 * i] , t[2 * i + 1]);
}
void add(int i , int l , int r , int tl , int tr , ll x){
int m = (l + r) / 2;
if(l > tr || r < tl) return;
if(l >= tl && r <= tr){
t[i] = x;
}else {
add(2 * i , l , m , tl , tr , x);
add(2 * i + 1 , m + 1 , r , tl , tr , x);
pushup(i);
}
}
ll get(int i , int l , int r , int tl , int tr){
int m = (l + r) / 2;
if(l > tr || r < tl) return 1e18;
if(l >= tl && r <= tr){
return t[i];
}else {
return min(get(2 * i , l , m , tl , tr) , get(2 * i + 1 , m + 1 , r , tl , tr));
}
}
ll query(int x , int y){
if(x > y)
return 1e18;
return get(1 , 1 , 1e5 , x , y);
}
void solve()
{
ll n , q , i , j ,l ,r , x , y , s = 0 , f , k , m , mx = 0 , mn = 1e18;
cin>>n>>m;
for(i = 1; i <= m; i++){
cin>>a[i]>>b[i]>>c[i];
v[a[i]].pb({b[i] , c[i]});
v[b[i]].pb({a[i] , c[i]});
s += (min(a[i] , b[i]) != i || max(b[i] , a[i]) != i + 1);
d[i] = i;
}
cin>>q;
s = (s == 0 && m == n - 1);
if(s)
for(i = 1; i <= m; i++)
add(1 , 1 , 1e5 , i , i , c[i]);
vector<pair<int,int>>vc;
for(j = 1; j <= q; j++){
cin>>k>>x>>y;
if(s){
if(k == 1){
c[x] = y;
add(1 , 1 , 1e5 , x , x , c[x]);
}else {
ll L = x, R= x;
if(c[x - 1] >= y && x != 1){
r = x - 1;
l = 1;
while(l != r){
ll m = (l + r) / 2;
if(query(m , x - 1) >= y)
r = m;
else
l = m + 1;
}
L = l;
}
if(x <= m && c[x] >= y){
l = x;
r = m;
while(l != r){
ll m = (l + r + 1) / 2;
if(query(x , m) >= y)
l = m;
else
r = m - 1;
}
R = l + 1;
}
cout<<R - l + 1<<"\n";
}
if(j == q)
return;
continue;
}
Q[j] = {x , y , j};
if(max(n , m) <= 1000 && q <= 10000){
if(k == 1){
c[x] = y;
}else {
for(i = 1; i <= n; i++)
p[i] = i , sz[i] = 1;
for(i = 1; i <= m; i++){
if(c[i] >= y){
join(a[i] , b[i]);
}
}
cout<<sz[get(x)]<<"\n";
}
if(j == q)
return;
}
}
sort(d + 1 , d + m + 1 , bmp);
sort(Q + 1 , Q + q + 1 , bmp1);
for(i = 1; i <= n; i++)
p[i] = i , sz[i] = 1;
l = 1;
for(i = 1; i <= m + 1; i++){
j = d[i];
while(l <= q && Q[l].y > c[j]){
ans[Q[l].k] = sz[get(Q[l].x)];
l++;
}
join(a[j] , b[j]);
if(i == m + 1)
continue;
}
for(j = 1; j <= q; j++)
cout<<ans[j]<<"\n";
}
int main(){
TL;
/*#ifndef ONLINE_JUDGE
freopen("input.txt", "r", stdin);
freopen("output.txt", "w", stdout);
#endif*/
int t = 1;
// cin>>t;
while(t--)
{
solve();
}
}
// Author : حسن
Compilation message
bridges.cpp: In function 'void solve()':
bridges.cpp:105:20: warning: variable 'L' set but not used [-Wunused-but-set-variable]
105 | ll L = x, R= x;
| ^
bridges.cpp:83:46: warning: unused variable 'f' [-Wunused-variable]
83 | ll n , q , i , j ,l ,r , x , y , s = 0 , f , k , m , mx = 0 , mn = 1e18;
| ^
bridges.cpp:83:58: warning: unused variable 'mx' [-Wunused-variable]
83 | ll n , q , i , j ,l ,r , x , y , s = 0 , f , k , m , mx = 0 , mn = 1e18;
| ^~
bridges.cpp:83:67: warning: unused variable 'mn' [-Wunused-variable]
83 | ll n , q , i , j ,l ,r , x , y , s = 0 , f , k , m , mx = 0 , mn = 1e18;
| ^~
bridges.cpp:130:25: warning: 'l' may be used uninitialized in this function [-Wmaybe-uninitialized]
130 | cout<<R - l + 1<<"\n";
| ~~^~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
6 ms |
13404 KB |
Output is correct |
| 2 |
Correct |
6 ms |
13404 KB |
Output is correct |
| 3 |
Correct |
53 ms |
13912 KB |
Output is correct |
| 4 |
Incorrect |
9 ms |
13656 KB |
Output isn't correct |
| 5 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
205 ms |
20596 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
52 ms |
22096 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
88 ms |
27868 KB |
Output is correct |
| 2 |
Incorrect |
35 ms |
15708 KB |
Output isn't correct |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
205 ms |
20596 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
6 ms |
13404 KB |
Output is correct |
| 2 |
Correct |
6 ms |
13404 KB |
Output is correct |
| 3 |
Correct |
53 ms |
13912 KB |
Output is correct |
| 4 |
Incorrect |
9 ms |
13656 KB |
Output isn't correct |
| 5 |
Halted |
0 ms |
0 KB |
- |
