Luogu P1886 滑动窗口

P1886 滑动窗口

现在有一堆数字共N个数字（N<=10^6），以及一个大小为k的窗口。现在这个从左边开始向右滑动，每次滑动一个单位，求出每次滑动后窗口中的最大值和最小值。

例如：

The array is [1 3 -1 -3 5 3 6 7], and k = 3.

输入输出格式

输入格式：

输入一共有两行，第一行为n,k。

第二行为n个数(<INT_MAX).

输出格式：

输出共两行，第一行为每次窗口滑动的最小值

第二行为每次窗口滑动的最大值

输入输出样例

输入样例#1：

8 3
1 3 -1 -3 5 3 6 7

输出样例#1：

-1 -3 -3 -3 3 3
3 3 5 5 6 7

说明

50%的数据，n<=10^5

100%的数据，n<=10^6

 1 //#pragma GCC optimize("O1")
 2 //#pragma GCC optimize("O2")
 3 //#pragma GCC optimize("O3")
 4 #include<cstdio>
 5 #include<cstring>
 6 #include<iostream>
 7 #include<algorithm>
 8 #include<ctime>
 9 #include<cmath>
10 #include<vector>
11 #include<queue>
12 //#include<stack>
13 //#include<map>
14 #define R(a,b,c) for(register int (a)=(b);(a)<=(c);++(a))
15 #define nR(a,b,c) for(register int (a)=(b);(a)>=(c);--(a))
16 #define Ii inline int
17 #define Iv inline void
18 #define Il inline long long
19 #define Ib inline bool
20 #define INF 0x3f3f3f3f
21 #define re register
22 #define ll long long
23 #define Max(a,b) ((a)>(b)?(a):(b))
24 #define Min(a,b) ((a)<(b)?(a):(b))
25 template<class Tp>Iv Cmax(Tp &a,Tp b){((a)=(a)>(b)?(a):(b));}
26 template<class Tp>Iv Cmin(Tp &a,Tp b){((a)=(a)<(b)?(a):(b));}
27 #define Fill(a,b) memset((a),(b),sizeof((a)))
28 #define D_e_Line printf("
-------------
");
29 #define D_e(x) printf("
______%d_______
",x)
30 #define Pause system("pause")
31 #define lson l,mid,rt<<1
32 #define rson mid+1,r,rt<<1|1
33 using namespace std;
34 const int N=1000005;
35 Ii read(){
36     int s=0,f=1;char c;
37     for(c=getchar();c>'9'||c<'0';c=getchar())if(c=='-')f=-1;
38     while(c>='0'&&c<='9')s=s*10+(c^'0'),c=getchar();
39     return s*f;
40 }
41 template<class Tp>Iv print(Tp x){
42     if(x<0)putchar('-'),x=-x;
43     if(x>9)print(x/10);
44     putchar(x%10^'0');
45 }
46 int t_max[N<<2],t_min[N<<2];
47 Iv pushup(int rt){
48     t_max[rt]=Max(t_max[rt<<1],t_max[rt<<1|1]),
49     t_min[rt]=Min(t_min[rt<<1],t_min[rt<<1|1]);
50 }
51 Iv updata(int x,int w,int l,int r,int rt){
52     if(l==r){t_max[rt]+=w,t_min[rt]+=w;return;}
53     int mid=l+r>>1;
54     x<=mid?updata(x,w,lson):updata(x,w,rson) ;
55     pushup(rt);
56 }
57 Ii query_max(int L,int R,int l,int r,int rt){
58     if(L<=l&&r<=R)return t_max[rt];
59     int mid=l+r>>1,maxium=-INF;
60     if(L<=mid)Cmax(maxium,query_max(L,R,lson));
61     if(R>mid)Cmax(maxium,query_max(L,R,rson));
62     return maxium;
63 }
64 Ii query_min(int L,int R,int l,int r,int rt){
65     if(L<=l&&r<=R)return t_min[rt];
66     int mid=l+r>>1,minium=INF;
67     if(L<=mid)Cmin(minium,query_min(L,R,lson));
68     if(R>mid)Cmin(minium,query_min(L,R,rson));
69     return minium;
70 }
71 int main(){
72     int n=read(),K=read();
73     R(i,1,n)
74         updata(i,read(),1,n,1);
75     int l=1,r=K;
76     while(1){
77         printf("%d ",query_min(l,r,1,n,1));
78         ++l,++r;
79         if(r>n)break;
80     }
81     putchar('
');
82     l=1,r=K;
83     while(1){
84         printf("%d ",query_max(l,r,1,n,1));
85         ++l,++r;
86         if(r>n)break;
87     }
88     return 0;
89 }

SegmentTree_80.cpp

 1 //#pragma GCC optimize("O1")
 2 //#pragma GCC optimize("O2")
 3 //#pragma GCC optimize("O3")
 4 #include<cstdio>
 5 #include<cstring>
 6 #include<iostream>
 7 #include<algorithm>
 8 #include<ctime>
 9 #include<cmath>
10 //#include<vector>
11 //#include<queue>
12 //#include<stack>
13 //#include<map>
14 #define R(a,b,c) for(register int (a)=(b);(a)<=(c);++(a))
15 #define nR(a,b,c) for(register int (a)=(b);(a)>=(c);--(a))
16 #define Ii inline int
17 #define Iv inline void
18 #define Il inline long long
19 #define Ib inline bool
20 #define INF 0x3f3f3f3f
21 #define re register
22 #define ll long long
23 #define Max(a,b) ((a)>(b)?(a):(b))
24 #define Min(a,b) ((a)<(b)?(a):(b))
25 template<class Tp>Iv Cmax(Tp &a,Tp b){((a)=(a)>(b)?(a):(b));}
26 template<class Tp>Iv Cmin(Tp &a,Tp b){((a)=(a)<(b)?(a):(b));}
27 #define Fill(a,b) memset((a),(b),sizeof((a)))
28 #define D_e_Line printf("
-------------
");
29 #define D_e(x) printf("
______%d_______
",x)
30 #define Pause system("pause")
31 #define lson l,mid,rt<<1
32 #define rson mid+1,r,rt<<1|1
33 using namespace std;
34 const int N=1000005;
35 Ii read(){
36     int s=0,f=1;char c;
37     for(c=getchar();c>'9'||c<'0';c=getchar())if(c=='-')f=-1;
38     while(c>='0'&&c<='9')s=s*10+(c^'0'),c=getchar();
39     return s*f;
40 }
41 template<class Tp>Iv print(Tp x){
42     if(x<0)putchar('-'),x=-x;
43     if(x>9)print(x/10);
44     putchar(x%10^'0');
45 }
46 int t_max[N<<2],t_min[N<<2];
47 int M;
48 Iv Build(int n){
49     for(M=1;M<=n+1;M<<=1);
50 }
51 Iv updata(int n,int w){
52     int tmp=n;
53     for(t_max[n+=M]+=w,n>>=1;n;n>>=1)
54         t_max[n]=Max(t_max[n<<1],t_max[n<<1|1]);
55     n=tmp;
56     for(t_min[n+=M]+=w,n>>=1;n;n>>=1)
57         t_min[n]=Min(t_min[n<<1],t_min[n<<1|1]);
58 }
59 Ii query_max(int s,int t){
60     int ans=-INF;
61     for(s+=M-1,t+=M+1;s^t^1;s>>=1,t>>=1){
62         if(~s&1)Cmax(ans,t_max[s^1]);
63         if(t&1)Cmax(ans,t_max[t^1]);
64     }
65     return ans;
66 }
67 Ii query_min(int s,int t){
68     int ans=INF;
69     for(s+=M-1,t+=M+1;s^t^1;s>>=1,t>>=1){
70         if(~s&1)Cmin(ans,t_min[s^1]);
71         if(t&1)Cmin(ans,t_min[t^1]);
72     }
73     return ans;
74 }
75 int main(){
76     int n=read(),K=read();
77     Build(n);
78     R(i,1,n)
79         updata(i,read());
80     int l=1,r=K;
81     while(1){
82         printf("%d ",query_min(l,r));
83         ++l,++r;
84         if(r>n)break;
85     }
86     putchar('
');
87     l=1,r=K;
88     while(1){
89         printf("%d ",query_max(l,r));
90         ++l,++r;
91         if(r>n)break;
92     }
93     return 0;
94 }

SegmentTree_ZKW_100.cpp

PS: POJ TLE