当前位置: 首页 > 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.jsqmd.com/news/42876/

相关文章:

  • 构造题 Codeforces2133E
  • 【LVGL】下拉列表部件
  • V8的垃圾回收器
  • 2025留学中介哪家好?厚仁/新通等5大品牌,多国联申/offer保障/名校申请/求职赋能全覆盖
  • 4th Universal Cup
  • 2025 最新滚珠丝杠厂家 推荐!重负载 / 精密 / 轧制 / 研磨滚珠丝杠全品类榜单,国产优质品牌实力测评与选购指南
  • 20232328 2025-2026-1 《网络与系统攻防技术》实验六实验报告
  • 这两个开源项目在世界互联网大会乌镇峰会获奖
  • #2338. [22NOIP十连 Day 1] 数列
  • 20232308 2025-2026-1 《网络与系统攻防技术》实验六实验报告
  • directory linux
  • deepin linux 安装
  • dbca linux
  • 智慧建筑工地传感器参数一览表
  • 2025靠谱留学机构推荐TOP5!美国/英国/澳洲多国申请,高录取率机构榜单
  • 04-import 和 export
  • 藜民百信消费帮扶平台:牵手 832 平台获殊荣,让兴和县农产品出圈、农户腰包鼓
  • Ollama 部署 Qwen3:0.6B 模型操作记录
  • LiveGBS GB28181监控视频平台中如何配置文字文印或图片水印,将水印叠加到播放器或视频内容中
  • Linux 项目部署
  • curtime在MySQL触发器中的使用方法
  • Frida Hook Android手册
  • curtime与now函数在MySQL中的区别
  • Trick 总结
  • 2025年最新出炉:车载电源十大品牌性能排行榜,光伏电源/氢能源车载直流转换器/新能源车载直流转换器/高功率密度电源/军用电源产品排行
  • 成都恒利泰PIN-to-PIN 国产版 HT-LFCW-5500+
  • 身份认证状态的存储与传递( Spring Boot篇 )
  • 国标GB28181算法算力平台EasyGBS打造园区智能化安防监控高效解决方案
  • 20232306 2025-2026-1 《网络与系统攻防技术》实验六实验报告
  • 数据库基础(lab5:单表查询 三)