2141: 排队 - #include <Seter> - using namespace Orz;
2141: 排队
http://www.zybbs.org/JudgeOnline/problem.php?id=2141
| RunID | User | Problem | Result | Memory | Time | Language | Code Length | Submit Time |
| 182939 | Seter | 2141 | Accepted | 9576 kb | 1136 ms | C/Edit | 3633 B | 2011-12-27 19:09:14 |
写了N天，花了N小时各种委以后决定换方法，然后写了1小时就A了……这题的数据范围暴力居然比树套树快T^T
动态维护逆序对数目。每次交换两个数。初始逆序对数归并排序暴力乱求，然后呢？
每次交换位于i,j上的两个数后，如果这两个数一样，那么等于没交换，否则呢？
最好自己想一想……（我一开始想错了，然后调了不下5个小时，囧）
考虑哪些数与Ai,Aj的逆序关系会变。1..i-1和j+1..n肯定是没有影响的（原来在前面还是在前面）。有影响的是（假设Ai<Aj）：
1.Ai,Aj，会产生一组逆序对
2.A(i+1..j-1)。这里有五种情况，可以构造出来：2 1 2 3 4 5 4，交换A1,A7，可以发现A2..6中，1和5没变，2和4各产生一组逆序对，3产生两组。
即，A(i+1..j-1)中，等于Ai或Aj的数会产生/消除一个逆序对，大小在Ai和Aj之间的数会产生/消除两个逆序对。
Ai<Aj时全部是产生逆序对，Ai>Aj时全部是消除逆序对。
于是可以树状数组/线段树套平衡树……也可以暴力找（会掉RP）……
一开始写的是每个节点记录数值外再记录一个编号，这样可以保证没有相同节点，调了N天后发生了灵异事件……
我用自己写的maker弄了个小数据出来，死循环了……于是我在自己感觉可能委掉的地方加了个putchar('!')来观察是否运行到了这个地方，另外没动，结果不死循环了……但是换一组数据又死循环……有没有神犇知道这个是神马意思！？
最后写了相同的数值合并在一个节点里，写了个手动堆，1Y……88行，也许是我写过最长的程序了吧……
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 | #include <stdio.h>#include <string.h>#define maxn 300000#define lt(a,b) ((a)==(b))#define cmp(a,b) ((a)<(b))#define icmp(a,b) ((a)<=(b))#define scmp(a,b) ((a)>(b))typedef struct _Splay{struct _Splay *c[2],*f;int s,v,k;}Splay,*PSplay;Splay null,st[maxn],*que[maxn],*a[20001];char str[300000],*p=str,*o=str;int bq=-1,eq=-1,n,f[20000],b[20000],t[20000],ans;inline PSplay updt(PSplay x){return x->s=x->c[0]->s+x->c[1]->s+x->k,x;}inline PSplay near(PSplay x,_Bool c){for(x=x->c[c];x->c[!c]!=&null;x=x->c[!c]);return x;}inline PSplay extr(PSplay x,_Bool c){while(x->c[c]!=&null)x=x->c[c];return x;}inline PSplay node(v){ if(++bq==maxn)bq=0; if(!que[bq])que[bq]=st+bq; que[bq]->f=que[bq]->c[0]=que[bq]->c[1]=&null; que[bq]->k=que[bq]->s=1; que[bq]->v=v; return que[bq];}inline PSplay rot(PSplay x){ PSplay fx=x->f,ffx=fx->f; _Bool c=fx->c[1]==x,fc=ffx->c[1]==fx; if(fx!=&null){ if((fx->c[c]=x->c[!c])!=&null)fx->c[c]->f=fx; if((x->f=ffx)!=&null)ffx->c[fc]=x; updt((fx->f=x)->c[!c]=fx); }return x;}inline PSplay splay(PSplay x,PSplay p){ if(x==&null)return x;for(;x->f!=p;rot(x))if(x->f->f!=p)rot((x->f->f->c[1]==x->f)==(x->f->c[1]==x)?x->f:x); return updt(x);}inline PSplay Join(PSplay x,PSplay y){ if(x==&null)return y;if(y==&null)return x;x=splay(extr(x,1),&null); return updt((x->c[1]=splay(y,&null))->f=x);}inline PSplay Remove(PSplay x){ if(x->k!=1)return x->k--,x->s--,x; if(++eq==maxn)eq=0;(que[eq]=x)->c[0]->f=x->c[1]->f=&null;return Join(x->c[0],x->c[1]);}inline PSplay Insert(PSplay r,int x){ _Bool c;if(!r||r==&null)return node(x); while(1){ if(lt(r->v,x))return r->k++,r->s++,splay(r,&null); if(r->c[c=cmp(r->v,x)]==&null)return splay(((r->c[c]=node(x))->f=r)->c[c],&null); r=r->c[c]; }}inline PSplay Find(PSplay*r,int x){ PSplay ans=&null,t=&null,f=(*r)->f; for(;*r!=&null;*r=t->c[cmp(t->v,x)])if(lt((t=*r)->v,x))return *r=splay(t,f); else if(icmp(t->v,x)&&(ans==&null||scmp(t->v,ans->v)))ans=t; *r=splay(ans==&null?t:ans,f);return ans;}void merge(i,j){ int c=i,mid=i+j>>1,k=mid,s=0;if(i+1==j)return;merge(i,mid);merge(mid,j); while(i!=mid){while(k!=j&&f[k]<f[i])t[s++]=f[k++];t[s++]=f[i++];ans+=k-mid;} memcpy(f+c,t,s<<2);}inline getint(){ int re=0; while(*p<'0'||*p>'9')p++; while(*p>='0'&&*p<='9')re=re*10+*p++-48; return re;}inline void BitInsert(i,x){for(i++;i<=n;i+=i&-i)a[i]=Insert(a[i],x);}inline void BitUpdate(i,x,y){for(i++;i<=n;i+=i&-i)a[i]=Remove(Find(a+i,x)),a[i]=Insert(a[i],y);}inline BitQuery(i,p,q){ int ans=0; for(i++;i;i-=i&-i){ if(Find(a+i,p)!=&null&&a[i]->v==p)ans+=a[i]->k; if(a[i]->v<=p)ans-=a[i]->c[0]->s+a[i]->k<<1; if(Find(a+i,q)!=&null&&a[i]->v==q)ans+=a[i]->k; if(a[i]->v<=q)ans+=a[i]->c[0]->s<<1; if(a[i]->v<q)ans+=a[i]->k<<1; }return ans;}inline void print(x){ char buf[11],*b=buf; if(!x)*o++=48;else{ while(x){*b++=x%10+48;x/=10;} while(b--!=buf)*o++=*b;} *o++='\n';}main(){ int i=-1,j,t,k,x,y;_Bool d;fread(p,1,300000,stdin); null.f=null.c[0]=null.c[1]=&null; for(n=getint();++i!=n;BitInsert(i,f[i]=b[i]=getint())); merge(0,n); for(t=getint();print(ans),t--;){ if(b[i=getint()-1]==b[j=getint()-1])continue; if(i>j)i^=j^=i^=j;x=(d=b[i]<b[j])?b[i]:b[j];y=d?b[j]:b[i]; k=1;if(j-1!=i)k+=BitQuery(j-1,x,y)-BitQuery(i,x,y); ans+=d?k:-k;BitUpdate(j,b[j],k=b[i]);BitUpdate(i,k,b[i]=b[j]);b[j]=k; }*--o=0;return puts(str),0;} |
By Seter
2012年1月24日 22:36
这题分成sqrt(n)块来也挺快的啦。。。
2012年1月25日 14:25
每块再用平衡树等维护？恩……