「BZOJ2141」排队
Description
排排坐，吃果果，生果甜嗦嗦，大家笑呵呵。你一个，我一个，大的分给你，小的留给我，吃完果果唱支歌，大家乐和和。红星幼儿园的小朋友们排起了长长地队伍，准备吃果果。不过因为小朋友们的身高有所区别，排成的队伍高低错乱，极不美观。设第i个小朋友的身高为hi，我们定义一个序列的杂乱程度为：满足ihj的(i,j)数量。幼儿园阿姨每次会选出两个小朋友，交换他们的位置，请你帮忙计算出每次交换后，序列的杂乱程度。为方便幼儿园阿姨统计，在未进行任何交换操作时，你也应该输出该序列的杂乱程度。
Input
第一行为一个正整数n，表示小朋友的数量；第二行包含n个由空格分隔的正整数h1,h2,…,hn，依次表示初始队列中小朋友的身高；第三行为一个正整数m，表示交换操作的次数；以下m行每行包含两个正整数ai和bi¬，表示交换位置ai与位置bi的小朋友。
Output
输出文件共m行，第i行一个正整数表示交换操作i结束后，序列的杂乱程度。
Sample Input
「样例输入」
3
130 150 140
2
2 3
1 3
3
130 150 140
2
2 3
1 3
Sample Output
1
0
3
「样例说明」
未进行任何操作时，(2,3)满足条件；
操作1结束后，序列为130 140 150，不存在满足i<j且hi>hj的(i,j)对；
操作2结束后，序列为150 140 130,(1,2)，(1,3)，(2,3)共3对满足条件的(i,j)。
「数据规模和约定」
对于100%的数据，1≤m≤2*103，1≤n≤2*104，1≤hi≤109，ai≠bi，1≤ai,bi≤n。
0
3
「样例说明」
未进行任何操作时，(2,3)满足条件；
操作1结束后，序列为130 140 150，不存在满足i<j且hi>hj的(i,j)对；
操作2结束后，序列为150 140 130,(1,2)，(1,3)，(2,3)共3对满足条件的(i,j)。
「数据规模和约定」
对于100%的数据，1≤m≤2*103，1≤n≤2*104，1≤hi≤109，ai≠bi，1≤ai,bi≤n。
题解
本题数据似乎不会出现h[i]相同的情况T T，为毛我要写finddown findup这些奇怪的东西
是我坑了，sort(a+l[x],a+r[x]) md排序都错了
写分块不写对拍简直作死wa了一版
不过这题分块跑得确实挺快的
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 101 102 103 104 105 106 107 108 109 110 111 112 113 114 115 116 117 118 119 120 121 122 123 124 125 126 127 128 129 130 131 132 133 134 135 136 137 138 139 140 141 142 143 144 145 146 147 148 149 150 151 152 |
#include<iostream> #include<cstdio> #include<cmath> #include<cstring> #include<cstdlib> #include<algorithm> #define ll long long #define inf 1000000000 using namespace std; inline int read() { int x=0,f=1;char ch=getchar(); while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();} while(ch>='0'&&ch<='9'){x=x*10+ch-'0';ch=getchar();} return x*f; } int n,m,block,cnt,ans; int l[605],r[605]; int a[20005],b[20005],t[20005],disc[20005],belong[20005]; inline int lowbit(int x){return x&(-x);} inline void update(int x,int val) { for(int i=x;i<=n;i+=lowbit(i)) t[i]+=val; } inline int query(int x) { int sum=0; for(int i=x;i;i-=lowbit(i)) sum+=t[i]; return sum; } inline int disc_find(int x) { int l=1,r=n; while(l<=r) { int mid=(l+r)>>1; if(disc[mid]==x)return mid; else if(disc[mid]<x)l=mid+1; else r=mid-1; } } int finddown(int l,int r,int x) { int ans=l-1,t=l; while(l<=r) { int mid=(l+r)>>1; if(a[mid]<x)ans=mid,l=mid+1; else r=mid-1; } return ans-t+1; } int findup(int l,int r,int x) { int ans=r+1,t=r; while(l<=r) { int mid=(l+r)>>1; if(a[mid]>x)ans=mid,r=mid-1; else l=mid+1; } return t-ans+1; } void rebuild(int x) { for(int i=l[x];i<=r[x];i++) a[i]=b[i]; sort(a+l[x],a+r[x]+1); } void pre() { for(int i=n;i;i--) { ans+=query(b[i]-1); update(b[i],1); } for(int i=1;i<=cnt;i++) rebuild(i); } void solve(int x,int y) { if(x==y)return; int L=r[belong[x]],R=l[belong[y]]; if(b[x]<b[y])ans++; if(b[x]>b[y])ans--; if(belong[x]==belong[y]) { for(int i=x+1;i<y;i++) { if(b[i]>b[x])ans++; if(b[i]<b[x])ans--; if(b[i]>b[y])ans--; if(b[i]<b[y])ans++; } } else { for(int i=x+1;i<=L;i++) { if(b[i]>b[x])ans++; if(b[i]<b[x])ans--; if(b[i]>b[y])ans--; if(b[i]<b[y])ans++; } for(int i=R;i<y;i++) { if(b[i]>b[x])ans++; if(b[i]<b[x])ans--; if(b[i]>b[y])ans--; if(b[i]<b[y])ans++; } for(int i=belong[x]+1;i<belong[y];i++) { ans-=finddown(l[i],r[i],b[x]); ans+=finddown(l[i],r[i],b[y]); ans+=findup(l[i],r[i],b[x]); ans-=findup(l[i],r[i],b[y]); } } swap(b[x],b[y]); rebuild(belong[x]);rebuild(belong[y]); } int main() { n=read(); block=sqrt(n); if(n%block)cnt=n/block+1; else cnt=n/block; for(int i=1;i<=cnt;i++) l[i]=(i-1)*block+1,r[i]=i*block; r[cnt]=n; for(int i=1;i<=n;i++) belong[i]=(i-1)/block+1; for(int i=1;i<=n;i++) disc[i]=a[i]=read(); sort(disc+1,disc+n+1); for(int i=1;i<=n;i++) a[i]=b[i]=disc_find(a[i]); pre(); printf("%d\n",ans); m=read(); for(int i=1;i<=m;i++) { int x=read(),y=read(); if(x>y)swap(x,y); solve(x,y); printf("%d\n",ans); } return 0; } |
计数器 9794032
OI 课件=>
OI 课件=>
这题有相同元素，果断被坑T_T
这题用bit+sgt更快而且更好写吧
比较爽T T
事实上这题分块跑得很快，而且如果题目说明没有相同元素代码会短几十行