当前位置: 首页 > 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.hn-smt.com/news/46177/

相关文章:

  • V8的垃圾回收器
  • 智慧建筑工地传感器参数一览表
  • curtime在MySQL触发器中的使用方法
  • 是时候从 MySQL 转到 PostgreSQL 18 了
  • 小学生兴趣班避坑指南:2025年实力机构TOP5,妙小程AI编程领衔推荐
  • OpenHarmony onDrag拖拽事件
  • 2025年四川硬芯线厂家排名前十权威评测及行业选择指南
  • 2025年江苏浙江上海地区留学服务商综合实力排行榜TOP10
  • 教育资源优质学习机品牌全面解析与实用指南:2025年11月最新版TOP5推荐榜单
  • PlantAssistant-管道数据文件PCF
  • 20251117noip模拟赛
  • 2025年智慧客房系统供应商口碑推荐榜单TOP10权威发布
  • 2025年知识变现新蓝海:阿卡德平台——普通人逆袭的黄金赛道
  • GPIO(下) - LI,Yi
  • 2025较好的留学机构有哪些大学
  • 每位工程师都会遇到的 10 个 Kubernetes 问题(及解决方法)【转】
  • 2025出国留学机构怎么样
  • 二十四、企业落地异地多活、异地容灾架构
  • uni-app 无法实现全局 Toast?这个方法做到了!
  • 2025成都有哪些留学中介机构比较好
  • 2025上海外贸快车公司十大排名,上海外贸独立站制作公司排行,谷歌SEO公司十大排名,独立站源头公司口碑推荐榜,谷歌独立站公司推荐榜:华企博网评选十大优质服务商
  • 说说Redis的集群方案?主从复制、哨兵、Cluster集群的区别和适用场景【转】
  • 2025年国内消波块钢模厂家综合实力排行榜:添元水泥领跑行业
  • 2025年欧式门窗定制厂家权威推荐:别墅平开窗/手摇平开窗/智能窗源头厂家精选
  • .py文件 linux
  • activiti使用oracle时数据迁移的注意事项
  • [Python刷题记录]-二叉树的最大深度-二叉树-简单
  • GPIO(上) - LI,Yi
  • 2025敏感肌面霜选购指南,从泛红到维稳全搞定!5大温和修护品牌实测
  • 2025成都最好的留学中介机构有哪些公司