bzoj3932 [ CQOI2015 ] --可持久化线段树
2018-06-17 23:29:31来源:未知 阅读 ()
题目大意:
#include<cstdio> #include<iostream> #include<cstring> #include<algorithm> #include<vector> using namespace std; #define N 100001 #define ll long long inline void Read(long long& x){ char c=getchar(); for(;c<'0'||c>'9';c=getchar()); for(x=0;c>='0'&&c<='9';x=(x<<3)+(x<<1)+c-48,c=getchar()); } inline void Read(int& x){ char c=getchar(); for(;c<'0'||c>'9';c=getchar()); for(x=0;c>='0'&&c<='9';x=(x<<3)+(x<<1)+c-48,c=getchar()); } vector<int>a1[N],a2[N]; struct node{ int l,r,s; ll w; }c[N*80]; struct gj{ int x,y,z; }b[N]; struct ls{ int w,f; }a[N]; int i,j,Rt[N],k,Num,n,m,M; ll Last=1,w2[N],x,y,z; inline void Update(int& Node,int l,int r,int x,int y){ c[++Num]=c[Node];Node=Num; c[Node].w+=w2[x]*y;c[Node].s+=y; if(l==r)return; int Mid=(l+r)>>1; if(x<=Mid)Update(c[Node].l,l,Mid,x,y);else Update(c[Node].r,Mid+1,r,x,y); } inline ll Query(int Node,int l,int r,int x){ if(l==r)return c[Node].w/c[Node].s*x; int Mid=(l+r)>>1; if(c[c[Node].l].s>x)return Query(c[Node].l,l,Mid,x);else if(c[c[Node].l].s==x)return c[c[Node].l].w;else return Query(c[Node].r,Mid+1,r,x-c[c[Node].l].s)+c[c[Node].l].w; } inline bool Cmp(ls a,ls b){ return a.w<b.w; } int main() { Read(m);Read(n); for(i=1;i<=m;i++)Read(b[i].x),Read(b[i].y),Read(b[i].z),a[i].w=b[i].z,a[i].f=i; sort(a+1,a+m+1,Cmp); for(i=1;i<=m;i++)if(a[i].w==a[i-1].w)b[a[i].f].z=M;else b[a[i].f].z=++M,w2[M]=a[i].w; for(i=1;i<=m;i++){ a1[b[i].x].push_back(b[i].z);a2[b[i].y+1].push_back(b[i].z); } for(i=1;i<=n;i++){ Rt[i]=Rt[i-1]; for(j=0;j<a1[i].size();j++)Update(Rt[i],1,M,a1[i][j],1); for(j=0;j<a2[i].size();j++)Update(Rt[i],1,M,a2[i][j],-1); } for(i=1;i<=n;i++){ Read(k);Read(x);Read(y);Read(z); x=((x*Last+y)%z)+1; if(c[Rt[k]].s<=x)Last=c[Rt[k]].w;else Last=Query(Rt[k],1,M,x); printf("%lld\n",Last); } return 0; }
标签:
版权申明:本站文章部分自网络,如有侵权,请联系:west999com@outlook.com
特别注意:本站所有转载文章言论不代表本站观点,本站所提供的摄影照片,插画,设计作品,如需使用,请与原作者联系,版权归原作者所有
- bzoj3932 [ CQOI2015 ] --可持久化线段树 2018-06-27
- bzoj4546 -- 可持久化字典树 2018-06-17
- [您有新的未分配科技点]可,可,可持久化!?------可持久化 2018-06-17
- 3674: 可持久化并查集加强版 2018-06-17
- hdu 6191--Query on A Tree(持久化字典树) 2018-06-17
IDC资讯: 主机资讯 注册资讯 托管资讯 vps资讯 网站建设
网站运营: 建站经验 策划盈利 搜索优化 网站推广 免费资源
网络编程: Asp.Net编程 Asp编程 Php编程 Xml编程 Access Mssql Mysql 其它
服务器技术: Web服务器 Ftp服务器 Mail服务器 Dns服务器 安全防护
软件技巧: 其它软件 Word Excel Powerpoint Ghost Vista QQ空间 QQ FlashGet 迅雷
网页制作: FrontPages Dreamweaver Javascript css photoshop fireworks Flash