fork download 
  1. #include <bits/stdc++.h>
  2. using namespace std;
  3.  
  4. #define foru(i,a,b) for(int i=(a); i<=(b); ++i)
  5. #define ford(i,a,b) for(int i=(a); i>=(b); --i)
  6. #define rep(i,a) for(int i=0; i<(a); ++i)
  7. #define bit(s,i) (((s)>>(i))&1)
  8. #define all(a) (a).begin(),(a).end()
  9. #define sz(a) (int)(a).size()
  10. #define ii pair<int,int>
  11. #define fi first
  12. #define se second
  13. #define eb emplace_back
  14. #define pb push_back
  15. #define ll long long
  16. #define __builtin_popcount(a) __builtin_popcountll(a)
  17. #define _ << " " <<
  18.  
  19. template <class X, class Y> bool maxi(X &x, Y y){return x<y?x=y,true:false;}
  20. template <class X, class Y> bool mini(X &x, Y y){return x>y?x=y,true:false;}
  21.  
  22. const int N=2e5+5;
  23.  
  24. int n,m,q; ll ans[N];
  25. vector<ii> que[N];
  26.  
  27. struct Edge{
  28.     int u,v,w;
  29.     bool operator < (const Edge &o) const {
  30.         return w < o.w;
  31.     }
  32. } edge[N];
  33.  
  34. int par[N]; ll mst;
  35. set<int> st[N];
  36. vector<ii> p[N];
  37.  
  38. int find(int a){
  39.     return par[a]==0 ? a : par[a]=find(par[a]);
  40. }
  41. void unite(int a, int b, int id){
  42.     a=find(a); b=find(b);
  43.     if(a==b) return;
  44.  
  45.     if(sz(st[a])>sz(st[b])) swap(a,b);
  46.  
  47.     for(int i:st[a]){
  48.         auto it=st[b].lower_bound(i);
  49.         if(it!=st[b].end()){
  50. //                cout<<i<<" "<<(*it)<<'\n';
  51.             p[i].eb(*it,id);
  52.         }
  53.         if(it!=st[b].begin()){
  54.             --it;
  55. //                cout<<(*it)<<" "<<i<<'\n';
  56.             p[*it].eb(i,id);
  57.         }
  58.     }
  59.  
  60.     par[a]=b;
  61.     for(int i:st[a]) st[b].insert(i);
  62.     st[a].clear();
  63.  
  64.     mst+=edge[id].w;
  65. }
  66.  
  67. int lstr[N];
  68. ll seg[N<<2];
  69.  
  70. void upd(int u, int v, int val, int id=1, int l=1, int r=n){
  71.     if(u>r||v<l) return;
  72.     if(u<=l&&r<=v){
  73.         seg[id]+=val;
  74.         return;
  75.     }
  76.     int mid=(l+r)>>1;
  77.     upd(u,v,val,id<<1,l,mid);
  78.     upd(u,v,val,id<<1|1,mid+1,r);
  79. }
  80.  
  81. ll get(int x){
  82.     int id=1, l=1, r=n; ll res=0;
  83.     while(l<r){
  84.         res+=seg[id];
  85.         int mid=(l+r)>>1;
  86.         if(x<=mid){
  87.             id=id<<1;
  88.             r=mid;
  89.         } else{
  90.             id=id<<1|1;
  91.             l=mid+1;
  92.         }
  93.     }
  94.     res+=seg[id];
  95.     return res;
  96. }
  97.  
  98. void solve(){
  99.     cin>>n>>m>>q;
  100.     foru(i,1,m){
  101.         cin>>edge[i].u>>edge[i].v>>edge[i].w;
  102.         ++edge[i].u; ++edge[i].v;
  103.     }
  104.     foru(i,1,q){
  105.         int l,r; cin>>l>>r;
  106.         ++l; ++r;
  107.         que[l].eb(r,i);
  108.     }
  109.  
  110.     sort(edge+1, edge+1+m);
  111.  
  112.     foru(i,1,n){
  113.         st[i].insert(i);
  114.     }
  115.     foru(i,1,m){
  116.         unite(edge[i].u, edge[i].v, i);
  117.     }
  118.  
  119.     foru(i,1,m) lstr[i]=n+1;
  120.     ford(l,n,1){
  121.         for(auto [r,id]:p[l]){
  122.             upd(r, lstr[id]-1, edge[id].w);
  123.             mini(lstr[id], r);
  124.         }
  125.         for(auto [r,id]:que[l]){
  126.             ans[id]=mst-get(r);
  127.         }
  128.     }
  129.  
  130.     foru(i,1,q) cout<<ans[i]<<'\n';
  131. }
  132.  
  133. int32_t main(){
  134.     #define task "test"
  135.     if(fopen(task".inp","r")){
  136.         freopen(task".inp","r",stdin);
  137.         freopen(task".out","w",stdout);
  138.     }
  139.     cin.tie(0)->sync_with_stdio(0);
  140.  
  141.     solve();
  142. }
  143.  
Success #stdin #stdout 0.01s 26064KB
comments (?)
stdin 
Standard input is empty
stdout 
Standard output is empty
https://ideone.com/qItPY2
language:
C++ (gcc 8.3)
created:
1 day ago
visibility:
public

Share or Embed source code

Discover > Sphere Engine API

The brand new service which powers Ideone!

Discover > IDE Widget

Widget for compiling and running the source code in a web browser!