1.與star in the window 差不多 降維 #include<stdio.h> #include<string.h> #include<algorithm> #include<vector> using namespace std; #define LL(x) (x<<1) #define RR(x) ((x<<1)|1)int n,m,p,q; int c; const int maxn=50005;struct Seg{int l,r;int max;int flag; }tree[maxn*4];void build(int l,int r,int k) {tree[k].flag=0;tree[k].max=0;tree[k].l=l;tree[k].r=r;if(l==r) return ;int mid=(l+r)>>1;build(l,mid,LL(k));build(mid+1,r,RR(k)); }int Max(int a,int b){if(a<b) return b;return a; }void push_down(int k) {if(tree[k].flag){tree[LL(k)].max+=tree[k].flag;tree[RR(k)].max+=tree[k].flag;tree[LL(k)].flag+=tree[k].flag;tree[RR(k)].flag+=tree[k].flag;tree[k].flag=0;} } void update(int l,int r,int k,int v) {if(l<=tree[k].l && tree[k].r<=r){tree[k].flag+=v;tree[k].max+=v;return ;}push_down(k);int mid=(tree[k].l+tree[k].r)>>1;if(l<=mid) update(l,r,LL(k),v);if(r>mid) update(l,r,RR(k),v);tree[k].max=Max(tree[LL(k)].max,tree[RR(k)].max); } int main() {int T;int i,j;int u,v;double ans;vector<int>x[maxn];scanf("%d",&T);while(T--){scanf("%d%d%d%d",&n,&m,&p,&q);scanf("%d",&c);for(i=0;i<=n;i++)x[i].clear();for(i=0;i<c;i++){scanf("%d%d",&u,&v);x[u].push_back(v);} build(1,m,1);ans=0;for(i=1;i<=n;i++){int a;sort(x[i].begin(),x[i].end());for(j=0;j<x[i].size();j++){a=j;while(a<x[i].size()-1 && x[i][a]+q-1>=x[i][a+1])a++;if(x[i][a]+q-1>=m)update(x[i][j],m,1,1);elseupdate(x[i][j],x[i][a]+q-1,1,1);j=a;}if(i>p){for(j=0;j<x[i-p].size();j++){a=j;while(a<x[i-p].size()-1 && x[i-p][a]+q-1>=x[i-p][a+1])a++;if(x[i-p][a]+q-1>=m)update(x[i-p][j],m,1,-1);else update(x[i-p][j],x[i-p][a]+q-1,1,-1);j=a;}}if(i>=p)ans+=tree[1].max;}printf("%.2lf\n",ans/(n-p+1));}return 0; }

總結

以上是生活随笔為你收集整理的Hit the Target!的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。