hdu5412CRB and Queries
2024-08-28 13:16:25
动态修改求区间K大。
整体二分是一个神奇的东西： http://www.cnblogs.com/zig-zag/archive/2013/04/18/3027707.html
入门：
一般的主席树都挂了，而且又难写。
南神的分析：http://blog.csdn.net/hdu2014/article/details/47834431 ORZ
然后对着板子写了一份：
1 #include<iostream>
2 #include<cstdio>
3 #include<algorithm>
4 #include<cmath>
5 #include<cstring>
6 #define maxn 450000
7 #define inf 2000000000
8 typedef long long ll;
9
10 using namespace std;
11 struct query
12 {
13 int x,y,k,s,tp,cur;
14 }q[maxn],q1[maxn],q2[maxn];
15 int a[maxn],ans[maxn],tmp[maxn],t[maxn];
16 int n,m,num,cnt;
17
18 void add(int x,int y)
19 {
20 for (int i=x;i<=n;i+=i&(-i)) t[i]+=y;
21 }
22 int ask(int x)
23 {
24 int s=;
25 for (int i=x;i>;i-=i&(-i)) s+=t[i];
26 return s;
27 }
28
29 void divide(int head,int tail,int l,int r)
30 {
31 if (head>tail) return;
32 if (l==r)
33 {
34 for (int i=head;i<=tail;i++)
35 if (q[i].tp==) ans[q[i].s]=l;
36 return;
37 }
38 int mid=(l+r)>>;
39 for (int i=head;i<=tail;i++)
40 {
41 if (q[i].tp==&&q[i].y<=mid) add(q[i].x,);
42 else
43 if (q[i].tp==&&q[i].y<=mid) add(q[i].x,-);
44 else
45 if (q[i].tp==) tmp[i]=ask(q[i].y)-ask(q[i].x-);
46 }
47
48 for (int i=head;i<=tail;i++)
49 {
50 if (q[i].tp==&&q[i].y<=mid) add(q[i].x,-);
51 else
52 if (q[i].tp==&&q[i].y<=mid) add(q[i].x,);
53 }
54
55 int l1,l2;
56 l1=l2=;
57 for (int i=head;i<=tail;i++)
58 if (q[i].tp==)
59 {
60 if (q[i].cur+tmp[i]>q[i].k-) q1[++l1]=q[i];
61 else
62 {
63 q[i].cur+=tmp[i];
64 q2[++l2]=q[i];
65 }
66 }
67 else
68 {
69 if (q[i].y<=mid) q1[++l1]=q[i];
70 else q2[++l2]=q[i];
71 }
72
73 for (int i=;i<=l1;i++) q[head+i-]=q1[i];
74 for (int i=;i<=l2;i++) q[head+i+l1-]=q2[i];
75 divide(head,head+l1-,l,mid);
76 divide(head+l1,tail,mid+,r);
77 }
78
79 int main()
80 {
81 while (scanf("%d",&n)!=EOF)
82 {
83 for (int i=;i<=n;i++) t[i]=;
84 memset(q,,sizeof(q));
85 memset(q1,,sizeof(q1));
86 memset(q2,,sizeof(q2));
87
88 num=cnt=;
89 for (int i=;i<=n;i++)
90 {
91 scanf("%d",&a[i]);
92 q[++num].x=i,q[num].y=a[i];
93 q[num].tp=;q[num].s=;
94 }
95 int ss,x,y,z;
96 scanf("%d",&m);
97 for (int i=;i<=m;i++)
98 {
99 scanf("%d",&ss);
if (ss==)
{
scanf("%d%d%d",&x,&y,&z);
q[++num].x=x,q[num].y=y,q[num].k=z;
q[num].tp=;q[num].s=++cnt;
}
else
{
scanf("%d%d",&x,&y);
q[++num].x=x;
q[num].y=a[x];
q[num].tp=;q[num].s=;
q[++num].x=x,q[num].y=y;
q[num].tp=,q[num].s=;
a[x]=y;
}
}
divide(,num,,inf);
for (int i=;i<=cnt;i++)
printf("%d\n",ans[i]);
}
return ;
123 }
2s左右。
最新文章
- Happy New Year 2016
- windows 录音程序（二）
- [ASE][Daily Scrum]11.13
- 用thinkphp进行微信开发的整体设计思考
- 双端队列（单调队列）poj2823 区间最小值（RMQ也可以）
- import package的问题
- TableView--通讯录--开篇
- IE,Chrome滚动条样式CSS
- JavaScript 函数方法 - bind()
- SQL Server 文件流文件组
- PHP静态化技术
- lesson - 9 课程笔记
- 流API--流的映射
- http post/get 2种使用方式
- 《java入门第一季》之好玩的正则表达式
- 如何利用Python网络爬虫抓取微信朋友圈的动态（上）
- ABP中的依赖注入思想
- Android getprop 读取的属性哪里来的？
- python基本数据类型之字符串（四）
- What I am concerned about