大码量题过多引起极度不适

Prince's Problem

题意：一个n个点的树，每个点有权值ai，给出Q次询问(u,v,w)求在路径u，v上的每一个点与w求gcd的积

题解：先把询问离线，做一个树上差分

然后分质因子考虑，发现只需要维护一下每种质因子的每种次幂有多少个

询问的时候做一个前缀和，再把大于当前w的p因子次幂的取一个min值即可

代码：（我不知道为什么写了3.5KB。。。）

#include<cstdio>
#include<cstring>
#include<algorithm>
#include<vector>
using namespace std;
inline int gi()
{char c;int num=0,flg=1;while((c=getchar())<'0'||c>'9')if(c=='-')flg=-1;while(c>='0'&&c<='9'){num=num*10+c-48;c=getchar();}return num*flg;
}
#define N 100005
#define M 10000005
const int mod=1000000007;
int ksm(int x,int y)
{int ret=1;while(y){if(y&1)ret=1ll*ret*x%mod;y>>=1;x=1ll*x*x%mod;}return ret;
}
int fir[N],to[2*N],nxt[2*N],cd[2*N],cnt;
void adde(int a,int b)
{to[++cnt]=b;nxt[cnt]=fir[a];fir[a]=cnt;to[++cnt]=a;nxt[cnt]=fir[b];fir[b]=cnt;
}
int fa[N],dep[N],son[N],siz[N],top[N];
void dfs1(int u)
{dep[u]=dep[fa[u]]+1;siz[u]=1;for(int v,p=fir[u];p;p=nxt[p]){if((v=to[p])!=fa[u]){fa[v]=u;dfs1(v);siz[u]+=siz[v];if(siz[son[u]]<siz[v])son[u]=v;}}
}
void dfs2(int u)
{if(son[u])top[son[u]]=top[u],dfs2(son[u]);for(int v,p=fir[u];p;p=nxt[p])if((v=to[p])!=fa[u]&&v!=son[u])top[v]=v,dfs2(v);
}
int LCA(int x,int y)
{while(top[x]!=top[y]){if(dep[top[x]]<dep[top[y]])swap(x,y);x=fa[top[x]];}return dep[x]<dep[y]?x:y;
}
int prime[N],tot;
bool vis[N];
void shai()
{int i,j,n=100000;vis[1]=1;for(i=2;i<=n;i++){if(!vis[i])prime[++tot]=i;for(j=1;j<=tot;j++){int tmp=i*prime[j];if(tmp>n)break;vis[tmp]=1;if(i%prime[j]==0)break;}}
}
int ans[N],inv[N];
int pr[N][10][2],apr[N][10][2];
vector<pair<int,int> > q[N];
int con[M];
vector<int> sum[M];
void solve(int u)
{int x,y;for(int i=1;i<=9;i++){if(!(x=apr[u][i][0]))break;sum[x][apr[u][i][1]]++;con[x]++;}for(int i=0;i<int(q[u].size());i++){int id=q[u][i].first,flg=q[u][i].second;for(int j=1;j<=9;j++){if(!(x=pr[id][j][0]))break;y=pr[id][j][1];int sumy=0,cnty=0;for(int k=1;k<=y;k++){sumy+=sum[x][k]*k;cnty+=sum[x][k];}if(flg==1)ans[id]=1ll*ans[id]*ksm(x,sumy+y*(con[x]-cnty))%mod;elseinv[id]=1ll*inv[id]*ksm(x,sumy+y*(con[x]-cnty))%mod;}}for(int v,p=fir[u];p;p=nxt[p])if((v=to[p])!=fa[u])solve(v);for(int i=1;i<=9;i++){if(!(x=apr[u][i][0]))break;sum[x][apr[u][i][1]]--;con[x]--;}
}
//#include<ctime>
//double c1;
int main()
{//c1=clock();//freopen("2.in","r",stdin);//freopen("2my.out","w",stdout);int n,i,j,k,u,v,Q,w,lca,mx=0;n=gi();shai();for(i=1;i<n;i++){u=gi();v=gi();adde(u,v);}dfs1(1);top[1]=1;dfs2(1);for(i=1;i<=n;i++){k=0;w=gi();for(j=1;prime[j]*prime[j]<=w;j++){if(w%prime[j]==0){mx=max(mx,prime[j]);apr[i][++k][0]=prime[j];while(w%prime[j]==0){apr[i][k][1]++;w/=prime[j];}con[prime[j]]=max(con[prime[j]],apr[i][k][1]);}}if(w>1){mx=max(mx,w);apr[i][++k][0]=w;apr[i][k][1]=1;con[w]=max(con[w],apr[i][k][1]);}}Q=gi();for(i=1;i<=Q;i++){ans[i]=inv[i]=1;u=gi();v=gi();lca=LCA(u,v);w=gi();q[u].push_back(make_pair(i,1));q[v].push_back(make_pair(i,1));q[lca].push_back(make_pair(i,-1));if(fa[lca])q[fa[lca]].push_back(make_pair(i,-1));k=0;for(j=1;prime[j]*prime[j]<=w;j++){if(w%prime[j]==0){mx=max(mx,prime[j]);pr[i][++k][0]=prime[j];while(w%prime[j]==0){pr[i][k][1]++;w/=prime[j];}con[prime[j]]=max(con[prime[j]],pr[i][k][1]);}}if(w>1){mx=max(mx,w);pr[i][++k][0]=w;pr[i][k][1]=1;con[w]=max(con[w],pr[i][k][1]);}}for(i=1;i<=mx;i++)if(con[i]>0){sum[i].resize(con[i]+2);con[i]=0;}solve(1);for(i=1;i<=Q;i++){ans[i]=1ll*ans[i]*ksm(inv[i],mod-2)%mod;printf("%d\n",ans[i]);}//printf("%.3fs\n",(clock()-c1)/1000);
}

Surprise me!

题意：

题解：莫反+虚树

先拆开phi(ab)

phi(ab)=phi(a)phi(b)*gcd(a,b)/phi(gcd(a,b))

看见gcd用一下莫反，提到前面去

最后化出来的式子就是：（今天莫名其妙打不了公式了，人眼识别latex将就着看吧。。）

\sum_{T=1}^n\sum{d|T}d*mu(T/d)/phi(d) * \sum{T|ai}\sum{T|aj}phi(ai)*phi(aj)*dis(i,j)

后面的一坨式子可以直接建虚树+换根DP

代码：（我不知道为什么写了3.3KB）

#include<cstdio>
#include<cstring>
#include<algorithm>
#include<vector>
using namespace std;
inline int gi()
{char c;int num=0,flg=1;while((c=getchar())<'0'||c>'9')if(c=='-')flg=-1;while(c>='0'&&c<='9'){num=num*10+c-48;c=getchar();}return num*flg;
}
#define N 200005
const int mod=1000000007;
int ksm(int x,int y)
{int ret=1;while(y){if(y&1)ret=1ll*ret*x%mod;y>>=1;x=1ll*x*x%mod;}return ret;
}
int prime[N],tot,mu[N],phi[N],inv[N];
bool vis[N];
void shai()
{int i,j,n=200000;inv[0]=inv[1]=phi[1]=mu[1]=1;vis[1]=1;for(i=2;i<=n;i++){inv[i]=1ll*(mod-mod/i)*inv[mod%i]%mod;if(!vis[i]){prime[++tot]=i;mu[i]=-1;phi[i]=i-1;}for(j=1;j<=tot;j++){int tmp=i*prime[j];if(tmp>n)break;vis[tmp]=1;if(i%prime[j]==0){mu[tmp]=0;phi[tmp]=phi[i]*prime[j];break;}mu[tmp]=(mod-mu[i])%mod;phi[tmp]=phi[i]*(prime[j]-1);}}
}
int a[N],fir[N],to[2*N],nxt[2*N],cd[2*N],cnt;
int dep[N],fa[N],top[N],siz[N],son[N];
void adde(int a,int b)
{if(dep[a]>dep[b])swap(a,b);to[++cnt]=b;nxt[cnt]=fir[a];fir[a]=cnt;cd[cnt]=dep[b]-dep[a];to[++cnt]=a;nxt[cnt]=fir[b];fir[b]=cnt;cd[cnt]=dep[b]-dep[a];
}
void dfs1(int u)
{dep[u]=dep[fa[u]]+1;siz[u]=1;for(int v,p=fir[u];p;p=nxt[p]){if((v=to[p])!=fa[u]){fa[v]=u;dfs1(v);siz[u]+=siz[v];if(siz[son[u]]<siz[v])son[u]=v;}}
}
int dfn[N],dc;
void dfs2(int u)
{dfn[u]=++dc;if(son[u])top[son[u]]=top[u],dfs2(son[u]);for(int v,p=fir[u];p;p=nxt[p])if((v=to[p])!=fa[u]&&v!=son[u])top[v]=v,dfs2(v);
}
int LCA(int x,int y)
{while(top[x]!=top[y]){if(dep[top[x]]<dep[top[y]])swap(x,y);x=fa[top[x]];}return dep[x]<dep[y]?x:y;
}
int stk[N],tp,dl[N],dcnt;
bool ont[N];
bool cmp(int x,int y){return dfn[x]<dfn[y];}
void build()
{tp=0;sort(dl+1,dl+dcnt+1,cmp);int i,u,lca,tmp=dcnt;if(dl[1]!=1)dl[++dcnt]=1,stk[++tp]=1;for(i=1;i<=tmp;i++){ont[u=dl[i]]=1;if(tp<=1||(lca=LCA(stk[tp],u))==stk[tp]){stk[++tp]=u;continue;}while(tp>1&&dep[stk[tp-1]]>=dep[lca]){adde(stk[tp-1],stk[tp]);tp--;}if(lca!=stk[tp]){adde(lca,stk[tp]);stk[tp]=lca;dl[++dcnt]=lca;}stk[++tp]=u;}while(tp>1){adde(stk[tp-1],stk[tp]);tp--;}
}
int val[N],f[N],g[N],sum[N],asum;
void CL()
{for(int u,i=1;i<=dcnt;i++){u=dl[i];fir[u]=val[u]=0;ont[u]=0;}dcnt=cnt=0;
}
vector<int> id[N];int w[N];
void DP1(int u,int ff)
{sum[u]=val[u];g[u]=f[u]=0;for(int v,p=fir[u];p;p=nxt[p]){if((v=to[p])!=ff){DP1(v,u);f[u]=(1ll*f[u]+1ll*f[v]+1ll*sum[v]*cd[p])%mod;sum[u]=(sum[u]+sum[v])%mod;}}
}
void DP2(int u,int ff)
{for(int v,p=fir[u];p;p=nxt[p]){if((v=to[p])!=ff){g[v]=(1ll*g[u]+1ll*(1ll*asum+2ll*mod-2ll*sum[v])*cd[p])%mod;DP2(v,u);}}
}
int main()
{int n,i,j,k,u,v;shai();n=gi();for(i=1;i<=n;i++)a[i]=gi(),id[a[i]].push_back(i);for(i=1;i<n;i++){u=gi();v=gi();adde(u,v);}dfs1(1);top[1]=1;dfs2(1);memset(fir,0,sizeof(fir));cnt=0;int ans=0,su;for(i=1;i<=n;i++){for(j=i;j<=n;j+=i){w[j]=(1ll*w[j]+1ll*i*inv[phi[i]]%mod*mu[j/i])%mod;for(k=0;k<int(id[j].size());k++){u=dl[++dcnt]=id[j][k];val[u]=phi[a[u]];}}build();DP1(1,0);g[1]=f[1];asum=sum[1];DP2(1,0);su=0;for(j=1;j<=dcnt;j++)if(ont[u=dl[j]])su=(1ll*su+1ll*g[u]*val[u])%mod;ans=(1ll*ans+1ll*su*w[i])%mod;CL();}ans=1ll*ans*inv[n]%mod*inv[n-1]%mod;printf("%d\n",(ans+mod)%mod);
}

Bear and Chemistry

• 给定一张 n 个点 m 条边的初始无向图。
• q 次询问，每次询问给定一个点集 V 和边集 E。
• 你需要判断，将 EE 中的边加入初始无向图之后，V 中任意两个点 x,y 是否都能在每条边至多经过一次的情况下从 x 到 yy 再回到 x。
• n,m,q,∑∣V∣,∑∣E∣≤3×105，强制在线。

题解：建边双树+在边双树上建虚树+再跑一遍tarjan

代码：（我不知道为什么写了3.9KB）

#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;
inline int gi()
{char c;int num=0,flg=1;while((c=getchar())<'0'||c>'9')if(c=='-')flg=-1;while(c>='0'&&c<='9'){num=num*10+c-48;c=getchar();}return num*flg;
}
#define N 300005
int fir[N],to[4*N],nxt[4*N],cnt;
void adde(int a,int b)
{to[++cnt]=b;nxt[cnt]=fir[a];fir[a]=cnt;to[++cnt]=a;nxt[cnt]=fir[b];fir[b]=cnt;
}int bel[N];// !!!
namespace BBC{int dfn[N],low[N],bbcno[N],stk[N],top,dc,bbccnt;void dfs(int u,int ff){dfn[u]=low[u]=++dc;stk[top++]=u;for(int v,p=fir[u];p;p=nxt[p]){if((p^1)==ff)continue;v=to[p];if(!dfn[v]){dfs(v,p);low[u]=min(low[u],low[v]);}else low[u]=min(low[u],dfn[v]);}if(dfn[u]==low[u]){bbccnt++;while(top>0){bbcno[stk[--top]]=bbccnt;if(stk[top]==u)break;}}}
}//----BBC----int root[N],nowrt,dep[N],fa[N],siz[N],son[N],top[N];
void dfs1(int u)
{root[u]=nowrt;dep[u]=dep[fa[u]]+1;siz[u]=1;for(int v,p=fir[u];p;p=nxt[p]){if((v=to[p])!=fa[u]){fa[v]=u;dfs1(v);siz[u]+=siz[v];if(siz[son[u]]<siz[v])son[u]=v;}}
}
int dfn[N],dc;
void dfs2(int u)
{dfn[u]=++dc;if(son[u])top[son[u]]=top[u],dfs2(son[u]);for(int v,p=fir[u];p;p=nxt[p])if((v=to[p])!=fa[u]&&v!=son[u])top[v]=v,dfs2(v);
}
int LCA(int x,int y)
{while(top[x]!=top[y]){if(dep[top[x]]<dep[top[y]])swap(x,y);x=fa[top[x]];}return dep[x]<dep[y]?x:y;
}
int dl[N],dcnt,stk[N],tp;bool ont[N];
bool cmp(int x,int y){return dfn[x]<dfn[y];}
void build()
{tp=0;sort(dl+1,dl+dcnt+1,cmp);int i,u,lca,tmp=dcnt;//if(dl[1]!=1)dl[++dcnt]=stk[++tp]=1;for(i=1;i<=tmp;i++){u=dl[i];ont[u]=1;if(root[u]!=root[dl[i-1]]){while(tp>1)adde(stk[tp-1],stk[tp]),tp--;tp=0;if(u!=root[u])dl[++dcnt]=stk[++tp]=root[u];}if(i<=1||(lca=LCA(stk[tp],u))==stk[tp]){stk[++tp]=u;continue;}while(tp>1&&dep[stk[tp-1]]>=dep[lca]){adde(stk[tp-1],stk[tp]);tp--;}if(lca!=stk[tp]){adde(lca,stk[tp]);stk[tp]=lca;dl[++dcnt]=lca;}stk[++tp]=u;}while(tp>1)adde(stk[tp-1],stk[tp]),tp--;
}
void CL()
{for(int i=1,u;i<=dcnt;i++){fir[u=dl[i]]=0;BBC::dfn[u]=BBC::bbcno[u]=BBC::low[u]=0;}cnt=1;dcnt=0;BBC::dc=BBC::top=BBC::bbccnt=0;
}
struct enode{int u,v;}e[N],etmp[N];
bool pd[N];int ptmp[N];
int main()
{//freopen("3.in","r",stdin);cnt=1;int n,m,Q,i,u,v;n=gi();m=gi();Q=gi();for(i=1;i<=m;i++){u=gi();v=gi();adde(u,v);e[i].u=u;e[i].v=v;}for(i=1;i<=n;i++)if(!dfn[i])BBC::dfs(i,0);cnt=1;memset(fir,0,sizeof(fir));memcpy(bel,BBC::bbcno,sizeof(BBC::bbcno));//printf("bel:");for(i=1;i<=n;i++)printf("%d ",bel[i]);printf("\n");for(i=1;i<=m;i++){int p=bel[e[i].u],q=bel[e[i].v];if(p!=q)adde(p,q);//,printf("adde:%d %d\n",p,q);}for(i=1;i<=BBC::bbccnt;i++){if(root[i])continue;nowrt=i;dfs1(i);top[i]=i;dfs2(i);}//printf("root:");for(i=1;i<=BBC::bbccnt;i++)printf("%d ",root[i]);printf("\n");memset(BBC::dfn,0,sizeof(BBC::dfn));memset(BBC::low,0,sizeof(BBC::low));memset(BBC::bbcno,0,sizeof(BBC::bbcno));BBC::dc=BBC::top=BBC::bbccnt=0;cnt=1;memset(fir,0,sizeof(fir));int R=0,nn,mm,cas=0;while(Q--){cas++;nn=gi();mm=gi();for(i=1;i<=nn;i++){u=ptmp[i]=bel[(gi()+R-1)%n+1];if(!pd[u])dl[++dcnt]=u,pd[u]=1;}for(i=1;i<=mm;i++){etmp[i].u=u=bel[(gi()+R-1)%n+1];etmp[i].v=v=bel[(gi()+R-1)%n+1];if(!pd[u])dl[++dcnt]=u,pd[u]=1;if(!pd[v])dl[++dcnt]=v,pd[v]=1;}build();for(i=1;i<=mm;i++){int p=etmp[i].u,q=etmp[i].v;if(p!=q)adde(p,q);//,printf("adde:%d %d\n",p,q);}for(i=1;i<=dcnt;i++)if(!BBC::dfn[dl[i]])BBC::dfs(dl[i],0);//printf("bbcno:");for(i=1;i<=n;i++)printf("%d ",BBC::bbcno[i]);printf("\n");bool flg=0;for(i=1;i<=nn;i++)if(BBC::bbcno[ptmp[i]]!=BBC::bbcno[ptmp[1]]){flg=1;break;}if(!flg){printf("YES\n");R=(R+cas)%n;}else printf("NO\n");CL();for(i=1;i<=nn;i++)pd[ptmp[i]]=0;for(i=1;i<=mm;i++)pd[etmp[i].u]=pd[etmp[i].v]=0;}
}

[NOI2019]弹跳

题面：https://www.luogu.com.cn/problem/P5471

题解：KD树优化建图，实际上可以不把边建出来，更新的时候直接在KD树上查询当前点可以到哪些点即可

代码：（比起前几道好多了。。。）

#include<cstdio>
#include<cstring>
#include<algorithm>
#include<queue>
#include<vector>
using namespace std;
inline int gi()
{char c;int num=0,flg=1;while((c=getchar())<'0'||c>'9')if(c=='-')flg=-1;while(c>='0'&&c<='9'){num=num*10+c-48;c=getchar();}return num*flg;
}
#define N 70005
#define M 150005
#define lc ch[i][0]
#define rc ch[i][1]
#define INF 0x3f3f3f3f
int n,D;
int tmp[N],tcnt;
int a[N][2],mx[N][2],mi[N][2];
int ch[N][2],rt;
void pushup(int i)
{mx[i][0]=max(max(mx[lc][0],mx[rc][0]),a[i][0]);mi[i][0]=min(min(mi[lc][0],mi[rc][0]),a[i][0]);mx[i][1]=max(max(mx[lc][1],mx[rc][1]),a[i][1]);mi[i][1]=min(min(mi[lc][1],mi[rc][1]),a[i][1]);
}
bool cmp(int x,int y){return a[x][D]<a[y][D];}
void build(int &i,int l,int r,int d)
{int mid=(l+r)>>1;D=d;nth_element(tmp+l,tmp+mid,tmp+r+1,cmp);i=tmp[mid];lc=rc=0;if(l<mid)build(lc,l,mid-1,d^1);if(mid<r)build(rc,mid+1,r,d^1);pushup(i);
}
int dis[N<<1];
struct node{int cd,l,r,u,d;}e[M];
vector<int> G[N];
priority_queue<pair<int,int> >q;
int qmx[2],qmi[2];
void fresh(int i,int k)
{if(qmx[0]<mi[i][0]||qmi[0]>mx[i][0]||qmx[1]<mi[i][1]||qmi[1]>mx[i][1])return;if(qmi[0]<=mi[i][0]&&mx[i][0]<=qmx[0]&&qmi[1]<=mi[i][1]&&mx[i][1]<=qmx[1]){if(dis[i+n]>k){dis[i+n]=k;q.push(make_pair(-k,i+n));}return;}if(qmi[0]<=a[i][0]&&a[i][0]<=qmx[0]&&qmi[1]<=a[i][1]&&a[i][1]<=qmx[1]){if(dis[i]>k){dis[i]=k;q.push(make_pair(-k,i));}}if(lc&&dis[lc+n]>k)fresh(lc,k);if(rc&&dis[rc+n]>k)fresh(rc,k);
}
int main()
{freopen("jump.in","r",stdin);freopen("jump.out","w",stdout);mx[0][0]=mx[0][1]=-INF;mi[0][0]=mi[0][1]=INF;int m,w,h,i,u,d,p;n=gi();m=gi();w=gi();h=gi();for(i=1;i<=n;i++){tmp[i]=i;a[i][0]=gi();a[i][1]=gi();}build(rt,1,n,0);for(i=1;i<=m;i++){G[gi()].push_back(i);e[i].cd=gi();e[i].l=gi();e[i].r=gi();e[i].d=gi();e[i].u=gi();}memset(dis,0x3f,sizeof(dis));dis[1]=0;q.push(make_pair(0,1));while(!q.empty()){u=q.top().second;d=-q.top().first;q.pop();if(d>dis[u])continue;if(u<=n){for(i=0;i<(int)G[u].size();i++){p=G[u][i];qmx[0]=e[p].r;qmx[1]=e[p].u;qmi[0]=e[p].l;qmi[1]=e[p].d;fresh(rt,d+e[p].cd);}}else{i=u-n;if(lc&&dis[lc+n]>d)dis[lc+n]=d,q.push(make_pair(-d,lc+n));if(rc&&dis[rc+n]>d)dis[rc+n]=d,q.push(make_pair(-d,rc+n));if(dis[i]>d)dis[i]=d,q.push(make_pair(-d,i));}}for(i=2;i<=n;i++)printf("%d\n",dis[i]);
}

Little Pony and Lord Tirek

题目背景

半人马提雷克是“我的小马驹：友谊是魔法”第四季最后两集的大反派。在“闪闪王国（上）”中，提雷克从塔他洛斯逃了出来。为了变得更加强大，他还吸取了小马们的魔法。

题目描述

提雷克的核心技能是法力吸取。这个技能可以吸收一个魔法生物的所有魔力并把它们交给施法者。

现在我们把这个问题简化，假设你有n只小马（编号从1到n）。每只小马有三种属性。

si：时间为0时这只小马拥有的法力值

mi：这只小马可以拥有的最大法力值

ri：这只小马单位时间内回复的法力值

提雷克会给出m条指令，每一条都可以被描述为3个整数：ti，li，ri。表示在时间为ti时，提雷克会从编号为li~ri的小马中吸取魔力（包括li，ri），我们会有序地给出m条指令，请你算出每一条指令之后提雷克可以吸取多少点魔力。

输入输出格式

输入格式：

第一行包含一个整数N（1 ≤ N ≤ 1e5）-小马的编号。接下来的n行每行包含三个整数Si， mi， ri（0 ≤ si ≤ mi ≤ 1e5；0 ≤ ri ≤ 1e5），表示 一只小马。

下一行包含一个整数m（1 ≤ M ≤ 1e5）-指令数。接下来的m行包含三个整数Ti， li， ri（0 ≤ ti ≤ 1e9；1 ≤ li ≤ ri ≤ N），表示提雷克的指令。所有的指令在ti递增的顺序下给出。

输出格式：

对于每一个指令，输出一行，包含一个整数：提雷克这一次一共吸收了多少魔力。

题解：（好像在ZROI讲过，但是当时自闭了没听懂。。。）

题解：ODT+主席树

考虑一段马在同一个时刻t1能量清零的情况，如果在t2时刻要将其再次清零

这一段马对答案的贡献就是Σmi   (ceil(mi/ri)<=t2-t1)  +  (t2-t1)*Σri  (ceil(mi/ri)>t2-t1)

发现这种形式是主席树可以简单维护的（因为所有马的属性是固定的）

而同一个时刻被清零的马的段是可以通过ODT维护的

0时刻的答案可以直接暴力（均摊O(n)）

注意ODT要先分离右边再分离左边，否则iterator会受到影响

注意初始时刻的答案计算方式

代码：

#include<cstdio>
#include<cstring>
#include<algorithm>
#include<set>
using namespace std;
inline int gi()
{char c;int num=0,flg=1;while((c=getchar())<'0'||c>'9')if(c=='-')flg=-1;while(c>='0'&&c<='9'){num=num*10+c-48;c=getchar();}return num*flg;
}
#define N 100005
#define LL long long
#define IT set<qnode>::iterator
#define pll pair<LL,LL>
struct anode{int s,m,r;
}val[N];
LL sumr[N];
struct qnode{int l,r,t;qnode(){}qnode(int a,int b,int c){l=a;r=b;t=c;}bool operator < (const qnode &T)const{return l<T.l;}
};
set<qnode> S;
IT split(int x)//x)[x
{IT it=S.lower_bound(qnode(x,x,0));if(it!=S.end()&&(*it).l==x) return it;qnode tmp=*--it;S.erase(it);S.insert(qnode(tmp.l,x-1,tmp.t));it=S.insert(qnode(x,tmp.r,tmp.t)).first;return it;
}
struct node{int l,r;LL sm,sr;
}a[N*19];
int T[N],tot;
void insert(int &i,int pre,int l,int r,int x,int km,int kr)
{if(i==pre) i=++tot,a[i]=a[pre];a[i].sm+=km;a[i].sr+=kr;if(l==r)return;int mid=(l+r)>>1;if(x<=mid)insert(a[i].l,a[pre].l,l,mid,x,km,kr);else insert(a[i].r,a[pre].r,mid+1,r,x,km,kr);
}
pll query(int i,int l,int r,int ql,int qr)
{if(!i||l>qr||r<ql)return make_pair(0ll,0ll);if(ql<=l&&r<=qr)return make_pair(a[i].sm,a[i].sr);int mid=(l+r)>>1;pll lans=query(a[i].l,l,mid,ql,qr);pll rans=query(a[i].r,mid+1,r,ql,qr);return make_pair(lans.first+rans.first,lans.second+rans.second);
}
const int lim=100000;
int main()
{//freopen("1.in","r",stdin);int n,i,m,x,y,t;n=gi();S.insert(qnode(n+1,2*lim,0));S.insert(qnode(0,0,0));for(i=1;i<=n;i++){val[i].s=gi();val[i].m=gi();val[i].r=gi();sumr[i]=sumr[i-1]+1ll*val[i].r;S.insert(qnode(i,i,0));T[i]=T[i-1];if(val[i].r)insert(T[i],T[i-1],0,lim,(val[i].m/val[i].r+(val[i].m%val[i].r!=0)),val[i].m,val[i].r);}m=gi();for(i=1;i<=m;i++){t=gi();x=gi();y=gi();IT r=split(y+1),l=split(x);LL ans=0;//printf("S.size:%d\n",S.size());for(IT it=l;it!=r;it++){qnode tmp=*it;//printf("tmp:l,r,t:%d %d %d\n",tmp.l,tmp.r,tmp.t);if(tmp.t==0)ans+=min(1ll*val[tmp.l].m,val[tmp.l].s+1ll*t*val[tmp.l].r);else{//[tmp.l,tmp.r]tmp.l--;pll retl=query(T[tmp.l],0,lim,0,t-tmp.t);pll ret=query(T[tmp.r],0,lim,0,t-tmp.t);ret.first-=retl.first;ret.second-=retl.second;ans+=1ll*(t-tmp.t)*((sumr[tmp.r]-sumr[tmp.l])-ret.second)+ret.first;}}S.erase(l,r);S.insert(qnode(x,y,t));printf("%lld\n",ans);}
}