题面
题解
我们把每个地雷向它能炸到的地雷连边，不难发现同一个强联通分量里的点只要一个炸全炸
那么我们缩点，首先所有入度为(0)的强联通分量中必须得选一个地雷炸掉，而入度不为(0)的强联通分量绝对会被某个入度为(0)的点连锁反应给炸掉，所以不用考虑
于是对于每个入度为(0)的点开一个(set)，维护里面的所有(c_i)，从每个(set)里取出最小的加入答案，修改也没问题了，于是有(50)分了
然而现在的问题是边数太多了，题解的做法是用线段树优化连边，于是就可以(AC)了
然而咱太菜了，并不会线段树优化连边，于是考虑了一个比较扯淡的办法
我们先把所有点按坐标排序，然后两两之间先把该连的边都连上
对于每个点，向左向右找到它最远能扩展的点，分别连边
一点正确性都没有，然而咱交上去竟然有(60)分
于是咱受到了鼓励，改了改，如果当前点和最远能拓展到的点之间的点数不超过(10)，那当前点直接把所有该连的都连了，否则就从这中间随机选取(10)个点连边
交上去竟然(A)了
反正是(IOI)赛制调参也方便
//minamoto
#include<bits/stdc++.h>
#define R register
#define ll long long
#define fp(i,a,b) for(R int i=a,I=b+1;i<I;++i)
#define fd(i,a,b) for(R int i=a,I=b-1;i>I;--i)
#define go(u) for(int i=head[u],v=e[i].v;i;i=e[i].nx,v=e[i].v)
template<class T>inline bool cmin(T&a,const T&b){return a>b?a=b,1:0;}
inline int abs(R int x){return x<0?-x:x;}
using namespace std;
char buf[1<<21],*p1=buf,*p2=buf;
inline char getc(){return p1==p2&&(p2=(p1=buf)+fread(buf,1,1<<21,stdin),p1==p2)?EOF:*p1++;}
int read(){
R int res,f=1;R char ch;
while((ch=getc())>'9'||ch<'0')(ch=='-')&&(f=-1);
for(res=ch-'0';(ch=getc())>='0'&&ch<='9';res=res*10+ch-'0');
return res*f;
}
char sr[1<<21],z[20];int K=-1,Z=0;
inline void Ot(){fwrite(sr,1,K+1,stdout),K=-1;}
void print(R ll x){
if(K>1<<20)Ot();if(x<0)sr[++K]='-',x=-x;
while(z[++Z]=x%10+48,x/=10);
while(sr[++K]=z[Z],--Z);sr[++K]='
';
}
const int N=1e5+5,M=6e6+5;
struct eg{int v,nx;}e[M];int head[N],tot;
inline void add(R int u,R int v){e[++tot]={v,head[u]},head[u]=tot;}
int dfn[N],low[N],col[N],st[N],p[N],r[N],c[N],deg[N];
int tim,n,q,top,cnt,x,y;multiset<int>s[N];ll ans;
void tarjan(int u){
dfn[u]=low[u]=++tim,st[++top]=u;
go(u)if(!dfn[v]){
tarjan(v),cmin(low[u],low[v]);
}else if(!col[v])cmin(low[u],dfn[v]);
if(dfn[u]==low[u]){
for(++cnt;st[top+1]!=u;--top)col[st[top]]=cnt;
}
}
struct node{
int p,id;
node(){}
node(int p,int id):p(p),id(id){}
friend bool operator <(const node &a,const node &b){return a.p<b.p;}
}a[N];
void add_edge(){
fp(i,1,n)a[i]=node(p[i],i);
sort(a+1,a+1+n);
fp(i,2,n-1){
if(abs(a[i].p-a[i-1].p)<=r[a[i].id])add(a[i].id,a[i-1].id);
if(abs(a[i].p-a[i+1].p)<=r[a[i].id])add(a[i].id,a[i+1].id);
}
if(abs(a[n].p-a[n-1].p)<=r[a[n].id])add(a[n].id,a[n-1].id);
if(abs(a[1].p-a[2].p)<=r[a[1].id])add(a[1].id,a[2].id);
fp(i,1,n){
int j=upper_bound(a+1,a+1+n,node(a[i].p+r[a[i].id],0))-a-1;
if(j!=i){
add(a[i].id,a[j].id);
if(j!=i+1){
if(j-i+1<=10){
fp(k,i+1,j-1)add(a[i].id,a[k].id);
}else{
int T=10;
while(T--){
int id=rand()%(j-i-1)+1+i;
add(a[i].id,a[id].id);
}
}
}
}
}
fp(i,1,n)a[i]=node(-p[i],i);
sort(a+1,a+1+n);
fp(i,1,n){
int j=upper_bound(a+1,a+1+n,node(a[i].p+r[a[i].id],0))-a-1;
if(j!=i){
add(a[i].id,a[j].id);
if(j!=i+1){
if(j-i+1<=10){
fp(k,i+1,j-1)add(a[i].id,a[k].id);
}else{
int T=10;
while(T--){
int id=rand()%(j-i-1)+1+i;
add(a[i].id,a[id].id);
}
}
}
}
}
}
int main(){
srand(time(0));
// freopen("testdata.in","r",stdin);
freopen("mines.in","r",stdin);
freopen("mines.out","w",stdout);
n=read(),q=read();
fp(i,1,n)p[i]=read(),r[i]=read(),c[i]=read();
// fp(i,1,n)fp(j,1,n)if(i!=j&&abs(p[i]-p[j])<=r[i])add(i,j);
add_edge();
fp(i,1,n)if(!dfn[i])tarjan(i);
fp(u,1,n)go(u)if(col[u]!=col[v])++deg[col[v]];
fp(i,1,n)if(!deg[col[i]])s[col[i]].insert(c[i]);
fp(i,1,cnt)ans+=*s[i].begin();
while(q--){
x=read(),y=read();
if(!deg[col[x]]){
ans-=*s[col[x]].begin();
s[col[x]].erase(s[col[x]].lower_bound(c[x]));
c[x]=y;
s[col[x]].insert(c[x]);
ans+=*s[col[x]].begin();
}
print(ans);
}
return Ot(),0;
}