教育网站制作价格,捕鱼游戏网站制作模板,中山网站设计,全屋定制都包括什么Description 有N个位置#xff0c;M个操作。操作有两种#xff0c;每次操作如果是1 a b c的形式表示在第a个位置到第b个位置#xff0c;每个位置加入一个数c如果是2 a b c形式#xff0c;表示询问从第a个位置到第b个位置#xff0c;第C大的数是多少。 Input 第一行N#…Description 有N个位置M个操作。操作有两种每次操作如果是1 a b c的形式表示在第a个位置到第b个位置每个位置加入一个数c如果是2 a b c形式表示询问从第a个位置到第b个位置第C大的数是多少。 Input 第一行NM接下来M行每行形如1 a b c或2 a b c Output 输出每个询问的结果 Sample Input 2 5 1 1 2 1 1 1 2 2 2 1 1 2 2 1 1 1 2 1 2 3 Sample Output 1 2 1 HINT 【样例说明】第一个操作 后位置 1 的数只有 1 位置 2 的数也只有 1 。 第二个操作 后位置 1的数有 1 、 2 位置 2 的数也有 1 、 2 。 第三次询问 位置 1 到位置 1 第 2 大的数 是1 。 第四次询问 位置 1 到位置 1 第 1 大的数是 2 。 第五次询问 位置 1 到位置 2 第 3大的数是 1 。 N,M50000,N,M50000abN1操作中abs(c)N2操作中cMaxlongint 解题思路 刚开始把题目看错了以为是区间加法差点没给我恶心死。 最后发现一个位置上可以有多个数。 那么这道题就是带修改整体二分。 将操作按时间序排序在二分过程中不要破坏这个序。 二分答案时将操作中的K若大于mid就插入线段树。 在时间序环境下查询区间。 剩下的就是普通整体二分了。 代码 1 #includecstdio2 #includecstring3 #includealgorithm4 #define lll spc15 #define rrr spc1|16 typedef long long lnt;7 const int N1000000;8 struct que{9 bool qu;10 int t;11 int l;12 int r;13 lnt x;14 }q[N],sp[N],ss[N];15 struct trnt{16 lnt val;17 lnt lzt;18 }tr[N];19 int sek[N];20 int ans[N];21 lnt num[N];22 int n,m;23 int cnt;24 int tot;25 void Add(int spc,int l,int r,lnt v){tr[spc].valv*(lnt)(r-l1);tr[spc].lztv;return ;}26 void pushup(int spc){tr[spc].valtr[lll].valtr[rrr].val;return ;}27 void pushdown(int spc,int l,int mid,int r)28 {29 if(tr[spc].lzt)30 {31 Add(lll,l,mid,tr[spc].lzt);32 Add(rrr,mid1,r,tr[spc].lzt);33 tr[spc].lzt0;34 }35 return ;36 }37 void update(int l,int r,int ll,int rr,int spc,lnt v)38 {39 if(llr||lrr)40 return ;41 if(lllrrr)42 {43 Add(spc,l,r,v);44 return ;45 }46 int mid(lr)1;47 pushdown(spc,l,mid,r);48 update(l,mid,ll,rr,lll,v);49 update(mid1,r,ll,rr,rrr,v);50 pushup(spc);51 return ;52 }53 lnt query(int ll,int rr,int l,int r,int spc)54 {55 if(lrr||llr)56 return 0;57 if(lllrrr)58 return tr[spc].val;59 int mid(lr)1;60 pushdown(spc,l,mid,r);61 return query(ll,rr,l,mid,lll)query(ll,rr,mid1,r,rrr);62 }63 bool cmp(que a,que b){if(a.qu!b.qu)return b.qu;return a.xb.x;}64 bool cmq(que a,que b){return a.tb.t;}65 void macrs(int l,int r,int ll,int rr)66 {67 if(llrr)68 return ;69 if(lr)70 {71 for(int ill;irr;i)72 if(q[i].qu)73 ans[q[i].t]l;74 return ;75 }76 int mid(lr)1;77 int sta10,sta20;78 for(int ill;irr;i)79 {80 if(q[i].qu)81 {82 lnt sumquery(q[i].l,q[i].r,1,n,1);83 if(q[i].xsum)84 ss[sta2]q[i];85 else{86 q[i].x-sum;87 sp[sta1]q[i];88 }89 }else{90 if(q[i].xmid)91 {92 update(1,n,q[i].l,q[i].r,1,1);93 ss[sta2]q[i];94 }else{95 sp[sta1]q[i];96 }97 }98 }99 for(int i1;ista2;i)
100 if(ss[i].qu0)
101 update(1,n,ss[i].l,ss[i].r,1,-1);
102 int stall-1;
103 for(int i1;ista1;i)
104 q[sta]sp[i];
105 int midlsta;
106 for(int i1;ista2;i)
107 q[sta]ss[i];
108 macrs(l,mid,ll,midl);
109 macrs(mid1,r,midl1,rr);
110 return ;
111 }
112 int main()
113 {
114 scanf(%d%d,n,m);
115 for(int i1;im;i)
116 {
117 int cmd;
118 scanf(%d,cmd);
119 sek[i]cmd;
120 scanf(%d%d%lld,q[i].l,q[i].r,q[i].x);
121 q[i].qu(cmd2);
122 q[i].ti;
123 }
124 std::sort(q1,qm1,cmp);
125 tot1;
126 num[1]q[1].x;
127 q[1].x1;
128 for(int i2;imq[i].qu0;i)
129 {
130 if(q[i].x!num[tot])
131 tot,num[tot]q[i].x;
132 q[i].xtot;
133 }
134 std::sort(q1,qm1,cmq);
135 macrs(1,tot,1,m);
136 for(int i1;im;i)
137 if(sek[i]2)
138 printf(%lld\n,num[ans[i]]);
139 return 0;
140 } 转载于:https://www.cnblogs.com/blog-Dr-J/p/10116110.html
