当前位置: 首页 > news >正文

P14521 【MX-S11-T2】加减乘除题解

当时思路想到了但是发现区间求交有点绕,给我绕晕了,我就只写了暴力就算了。

其实就是对区间进行取交集,之后离散化后在值域树状数组上求前缀个数即可。

#include<bits/stdc++.h>
#define ll long long
#define int ll
#define ls p<<1
#define rs p<<1|1
#define re register 
#define pb push_back
#define pir pair<int,int> 
#define f(a,x,i) for(int i=a;i<=x;i++)
#define fr(a,x,i) for(int i=a;i>=x;i--)
#define fi first
#define se second
#define lowbit(x) (x&-x)
using namespace std;
const int N=5e5+10;
const int M=5e6+10;
const int mod=1e9+7;
const int INF=1e9+7;
mt19937 rnd(251);int n,m;struct ss{int op,x,l=114514,r=-114514;
}a[N];struct sss{int y,l,r;
};
vector<sss> g[N];int quest[M];
unordered_map<int,int> rns;vector<int> val;
int len;pair<int,int> jiao(int l,int r,int pl,int pr){return make_pair(max(l,pl),min(r,pr));
}void dfs(int x,int d){for(int i=0;i<g[x].size();i++){int y=g[x][i].y;int k=a[x].op*a[x].x;int l=g[x][i].l-k,r=g[x][i].r-k;pair<int,int> ans=jiao(l,r,a[x].l+d,a[x].r+d);if(ans.fi>ans.se) continue;a[y].l=ans.fi-d;a[y].r=ans.se-d;dfs(y,d+k);for(int i=1;i<=n;i++){}}
}int t[M];void add(int x,int k){while(x<=len){t[x]+=k;x+=lowbit(x);}
} int query(int x){int sum=0;while(x){sum+=t[x];x-=lowbit(x);}return sum;
}void solve(){cin>>n>>m;for(int i=2;i<=n;i++){int x,l,r;cin>>x>>l>>r;g[x].push_back({i,l,r});}for(int i=1;i<=n;i++){char c;cin>>c>>a[i].x;a[i].op=((c=='-')?-1:1);}for(int i=1;i<=m;i++){cin>>quest[i];val.push_back(quest[i]);}a[1].l=-2e18-5;a[1].r=2e18+5;dfs(1,0);for(int i=1;i<=n;i++){val.push_back(a[i].l);val.push_back(a[i].r);val.push_back(a[i].r+1);} for(int i=1;i<=n;i++){sort(a+1,a+1)}sort(val.begin(),val.end());len=unique(val.begin(),val.end())-val.begin();for(int i=0;i<len;i++){rns[val[i]]=i+1;}for(int i=1;i<=n;i++){a[i].l=rns[a[i].l];a[i].r=rns[a[i].r];}for(int i=1;i<=m;i++){quest[i]=rns[quest[i]];}for(int i=1;i<=n;i++){if(a[i].r<a[i].l){continue;}add(a[i].l,1);add(a[i].r+1,-1);}for(int i=1;i<=m;i++){cout<<query(quest[i])<<"\n";}} signed main(){
//  	freopen("kingdom3.in","r",stdin);
//  	freopen("a.out","w",stdout);ios::sync_with_stdio(0);cin.tie(nullptr);   int t=1;
//	cin>>t;while(t--){solve();} return 0;
}
http://www.gsyq.cn/news/52292.html

相关文章:

  • V8的垃圾回收器
  • 2025留学中介哪家好?厚仁/新通等5大品牌,多国联申/offer保障/名校申请/求职赋能全覆盖
  • 4th Universal Cup
  • 20232328 2025-2026-1 《网络与系统攻防技术》实验六实验报告
  • #2338. [22NOIP十连 Day 1] 数列
  • 20232308 2025-2026-1 《网络与系统攻防技术》实验六实验报告
  • 04-import 和 export
  • LiveGBS GB28181监控视频平台中如何配置文字文印或图片水印,将水印叠加到播放器或视频内容中
  • Linux 项目部署
  • curtime在MySQL触发器中的使用方法
  • Frida Hook Android手册
  • Trick 总结
  • 身份认证状态的存储与传递( Spring Boot篇 )
  • 国标GB28181算法算力平台EasyGBS打造园区智能化安防监控高效解决方案
  • ubuntu18解决 libc.so.6: version `GLIBC_2.28‘ not found
  • curl linux 命令
  • 2025年不锈钢网带链板制造企业权威推荐榜单:不锈钢平顶链板/ 链板/304不锈钢链板源头厂家精选
  • 算法课 PA2 T1
  • OpenAI Responses API 的战略意图与技术架构:AI 智能体时代的技术范式变革
  • JDK17 ProcessBuilder执行脚本报错 error=13
  • 2025年CNBD权威公开:淮安婚纱照拍摄十佳机构专业评测,弥素摄影工作室蝉联冠军宝座
  • cmake 安装 linux
  • docker compose, minikube, kind, dev containers, wsl2
  • 小学生兴趣班避坑指南:2025年实力机构TOP5,妙小程AI编程领衔推荐
  • 2025年11月安检门最新推荐厂家,手机安检门、贵金属安检门、高精度安检门、食品厂安检门、保密场所专用安检门​
  • fastadmin下的多级联动
  • NOIP 模拟赛 7 总结
  • 20232314 2025-2026-1 《网络与系统攻防技术》实验六实验报告
  • 2025年在淮安婚纱照拍摄团队公司实力盘点,弥素摄影工作室领衔十大精品机构
  • 当下山西比较好的纪念馆展示柜工厂排行榜揭晓