Description
n ,Q<=1e5
Solution
- 有一种显然的做法，每一个点对于它能引爆的点连一条有向边，得到一个有向图。
- Tarjan缩点后，对于每一个强联通分量，贡献就是这里面的点权最小值。
- 只有入度为0的强联通分量才会有贡献。然后在线用一个multiset维护一下每一个强联通分量的的最小值。
- 这种方法是N*N+NlogQ的。
- 瓶颈在于前面缩点的N*N
- 注意到所有连的边的范围都是一个连续的区间，我们可以建立一颗线段树，将边连到线段树上对应区间的结点上。
- 一共会有NlogN个点，每个点也最多连出去logN条边，就可以做到NlogN
#include<cstdio>
#include<cmath>
#include<cstring>
#include<algorithm>
#include<set>
#define maxn 100005
#define maxm 2000000
#define LL long long
using namespace std;
struct arr{
int p,r,c,i;
} a[maxn];
int n,q,i,j,k,x,y,tot,num[maxm],w[maxn];
int cmp(arr a,arr b){return a.p<b.p;}
int e[maxm*2],em,nx[maxm*2],ls[maxm];
int tot0,cnt,vis[maxm],bz[maxm],d[maxm],low[maxm],dfn[maxm],fr[maxm];
multiset<int> g[maxn];
set<int> :: iterator it;
int du[maxn];
LL ans;
int read(){
int s=0; char ch=getchar();
while (ch<'0'||ch>'9') ch=getchar();
while (ch>='0'&&ch<='9') s=s*10+ch-'0',ch=getchar();
return s;
}
void insert(int x,int y){em++; e[em]=y; nx[em]=ls[x]; ls[x]=em;}
void link(int x,int l,int r,int ll,int rr,int p){
if (l>rr||r<ll) return;
if (ll<=l&&r<=rr) {
if (l==r) insert(p,l); else{
if (!num[x]) num[x]=++tot;
insert(p,num[x]);
}
return;
}
int mid=(l+r)/2;
link(x*2,l,mid,ll,rr,p); link(x*2+1,mid+1,r,ll,rr,p);
}
void cover(int x,int l,int r){
if (l==r) return;
int mid=(l+r)/2;
if (l==mid) num[x*2]=l;
if (mid+1==r) num[x*2+1]=r;
if (num[x]){
if (!num[x*2]) num[x*2]=++tot;
if (!num[x*2+1]) num[x*2+1]=++tot;
insert(num[x],num[x*2]);
insert(num[x],num[x*2+1]);
}
cover(x*2,l,mid),cover(x*2+1,mid+1,r);
}
void tarjan(int x){
vis[x]=1,d[++d[0]]=x,bz[x]=1,low[x]=dfn[x]=++cnt;
for(int i=ls[x];i;i=nx[i]) {
if (!vis[e[i]]) tarjan(e[i]),low[x]=min(low[x],low[e[i]]);
else if (bz[e[i]]) low[x]=min(low[x],dfn[e[i]]);
}
if (low[x]==dfn[x]){
tot0++;
while (d[d[0]]!=x) {
int y=d[d[0]--];
fr[y]=tot0,bz[y]=0;
if (y<=n) g[tot0].insert(a[y].c);
}
d[0]--;
fr[x]=tot0,bz[x]=0;
if (x<=n) g[tot0].insert(a[x].c);
}
}
int main(){
freopen("mines.in","r",stdin);
freopen("mines.out","w",stdout);
n=read(),q=read();
for(i=1;i<=n;i++) a[i].p=read(),a[i].r=read(),a[i].c=read(),a[i].i=i;
sort(a+1,a+1+n,cmp);
for(i=1;i<=n;i++) w[a[i].i]=i;
tot=n;
for(i=2;i<=n;i++) {
int l=1,r=i-1;
while (l<r-1) if (a[(l+r)/2].p>=a[i].p-a[i].r) r=(l+r)/2;
else l=(l+r)/2+1;
if (a[l].p>=a[i].p-a[i].r) link(1,1,n,l,i-1,i);
else if (a[r].p>=a[i].p-a[i].r) link(1,1,n,r,i-1,i);
}
for(i=1;i<n;i++){
int l=i+1,r=n;
while (l<r-1) if (a[(l+r)/2].p<=a[i].p+a[i].r) l=(l+r)/2;
else r=(l+r)/2-1;
if (a[r].p<=a[i].p+a[i].r) link(1,1,n,i+1,r,i);
else if (a[l].p<=a[i].p+a[i].r) link(1,1,n,i+1,l,i);
}
cover(1,1,n);
cnt=0;
for(i=1;i<=tot;i++) if (!vis[i]) tarjan(i);
for(i=1;i<=tot;i++)
for(j=ls[i];j;j=nx[j]) if (fr[e[j]]!=fr[i])
du[fr[e[j]]]++;
for(i=1;i<=tot0;i++) if (du[i]==0) {
it=g[i].begin();
ans+=(LL)*it;
}
while (q--){
scanf("%d%d",&x,&y);
x=w[x];
if (du[fr[x]]==0){
it=g[fr[x]].begin();
ans-=(LL)*it;
it=g[fr[x]].find(a[x].c);
g[fr[x]].erase(it);
a[x].c=y;
g[fr[x]].insert(a[x].c);
it=g[fr[x]].begin();
ans+=(LL)*it;
}
printf("%lld
",ans);
}
}