题解 P3353 【在你窗外闪耀的星星】
Suuon_Kanderu
2020-01-29 21:51:37
发现没有分块的，赶紧水题解，数据较小，几乎什么都能跑。分块是一种暴力优化算法，简单容易码，
具体就是把数据分成$\sqrt{n}$个块，查询时暴力查询前面的不完整数据，后面的不完整数据，再加上中间的整块~~最适合我这种懒人~~
这是我的板子，把最大最小和一块维护了。
```c
#include<stdio.h>
#include<iostream>
#include<algorithm>
#include<cmath>
#include<string.h>
using namespace std;
const int N=100000+100;
struct fk{//分块大法
int num,rank;//数值，第几块 ,＋数的标记
}a[N];
int minn[N],sum[N],maxx[N],tag[N],b[N];//第一块的最最小值，和，最大值，标记
#define rank(i) a[i].rank
#define num(i) a[i].num
#define minn(i) minn[i]
#define sum(i) sum[i]
#define maxx(i) maxx[i]
#define tag(x) tag[x]
int n,bs,zo;//共有几个数，块的大小 ,总共有几个块
int qsum(int l,int r) {
int ans=0,k1,k2;
for(int i=l;; i++) {
k1=i;
if(rank(i+bs-1)==rank(i))break;//如果这是块的第一个元素，break
ans+=num(i)+tag(rank(i));
}
for(int i=r;; i--) {
k2=i;
if(rank(i-bs+1)==rank(i))break;//同上
ans+=num(i)+tag(rank(i));
}
k1++;
k2--;
k1=rank(k1);
k2=rank(k2);
for(; k1<=k2; k1++) {
ans+=sum(k1);//sum在修改时已经维护过了，不用再加tag
}
return ans;
}
int qmax(int l,int r) {//忽略
int ans=-0x7fffffff,k1,k2;
for(int i=l;; i++) {
k1=i;
if(rank(i+bs-1)==rank(i))break;
ans=max(num(i)+tag(rank(i)),ans);
}
for(int i=r;; i--) {
k2=i;
if(rank(i-bs+1)==rank(i))break;
ans=max(num(i)+tag(rank(i)),ans);
}
k1++;
k2--;
k1=rank(k1);
k2=rank(k2);
for(; k1<=k2; k1++) {
ans=max(maxx(k1),ans);
}
return ans;
}
int qmin(int l,int r) {//忽略
int ans=0x7fffffff,k1,k2;
for(int i=l;; i++) {
k1=i;
if(rank(i+bs-1)==rank(i))break;
ans=min(num(i)+tag(rank(i)),ans);
}
for(int i=r;; i--) {
k2=i;
if(rank(i-bs+1)==rank(i))break;
ans=min(num(i)+tag(rank(i)),ans);
}
k1++;
k2--;
k1=rank(k1);
k2=rank(k2);
for(; k1<=k2; k1++) {
ans=min(minn(k1),ans);
}
return ans;
}
void change(int x,int y) { //a[x]+=y;忽略
num(x)+=y;
sum(rank(x))+=y;
minn(rank(x))=min(num(x)+tag(rank(x)),minn(rank(x)));
maxx(rank(x))=max(num(x)+tag(rank(x)),maxx(rank(x)));
}
void change2(int l,int r,int z) { //i from x to y a[i]+=z
int k1,k2;
for(int i=l;; i++) {
k1=i;
if(rank(i+bs-1)==rank(i))break;//同上qsum函数
num(i)+=z;;
sum(rank(i))+=z;
if(num(i)>maxx(rank(i)))maxx(rank(i))=num(i);
if(num(i)<maxx(rank(i)))minn(rank(i))=num(i);
}
for(int i=r;; i--) {
k2=i;
if(rank(i-bs+1)==rank(i))break;//同上
num(i)+=z;
sum(rank(i))+=z;
if(num(i)>maxx(rank(i)))maxx(rank(i))=num(i);
if(num(i)<maxx(rank(i)))minn(rank(i))=num(i);
}
k1++;k2--;
k2=rank(k2);
k1=rank(k1);
for(; k1<=k2; k1++) {
tag(k1)+=z;
sum(k1)+=bs*z;
minn(k1)+=z;
maxx(k1)+=z;
}
}
void pr() {//调试用
printf("\tid\tnum\trank\n");
for(int i=1; i<=n; i++)printf("\t%d:\t%d\t%d\n",i,num(i),rank(i));
printf("\n\tid\tmin\tmax\tsum\ttag\n");
for(int i=1; i<=zo; i++)printf("\t%d:\t%d\t%d\t%d\t%d\n",i,minn(i),maxx(i),sum(i),tag(i));
}
signed main(){
int max1=-1,x,y,k;
cin>>n>>k;bs=sqrt(n);
if(n/bs*bs==n)zo=n/bs; else zo=n/bs+1;
for(int i=1;i<=n;i++){
cin>>x>>y;
b[x]+=y;
max1=max(x,max1);
}
for(int i=1;i<=max1;i++)num(i)=b[i];
for(int i=1;i<=x;i++){
if((i-1)%bs==0){
minn((i-1)/bs+1)=0x7fffffff;
maxx((i-1)/bs+1)=-0x7fffffff;
sum((i-1)/bs+1)=0;
}
a[i].rank=(i-1)/bs+1;
minn((i-1)/bs+1)=min(num(i),minn((i-1)/bs+1));
maxx((i-1)/bs+1)=max(num(i),maxx((i-1)/bs+1));
sum((i-1)/bs+1)+=num(i);
}
int l,r,e,ans=0;
for(int i=1;i+k-1<=max1;i++){
ans=max(ans,qsum(i,i+k-1));
}
cout<<ans<<endl;
return 0;
}
```