1 Show Code - Run ID 1166912
2
3 Submit Time: 2012-02-18 01:33:04 Language: GNU C Result: Accepted
4 Pid: 3124 Time: 0.00 sec. Memory: 852 K. Code Length: 0.6 K.
5 # include <stdio.h>
6 # define cross(x1,y1,x2,y2) (x1)*(y2)-(x2)*(y1)
7 # define get_aera(x0,y0,x1,y1,x2,y2) (cross((x1)-(x0),(y1)-(y0),(x2)-(x0),(y2)-(y0)))
8 int main()
9 {
10 int n;
11 while(scanf("%d",&n)!=EOF&&n)
12 {
13 int i;
14
15 double x[3],y[3],aera=0;
16 scanf("%lf%lf",&x[2],&y[2]);
17 for(i=1;i<n;i++)
18 {
19 scanf("%lf%lf",&x[i%2],&y[i%2]);
20 if(i>1) aera+=get_aera(x[2],y[2],x[(i+1)%2],y[(i+1)%2],x[i%2],y[i%2]);
21 }
22 aera*=0.5;
23 if(aera<0) aera=-aera;
24 printf("%.0f\n",aera+1e-8);
25
26 }
27 return 0;
28 }
2
3 Submit Time: 2012-02-18 01:33:04 Language: GNU C Result: Accepted
4 Pid: 3124 Time: 0.00 sec. Memory: 852 K. Code Length: 0.6 K.
5 # include <stdio.h>
6 # define cross(x1,y1,x2,y2) (x1)*(y2)-(x2)*(y1)
7 # define get_aera(x0,y0,x1,y1,x2,y2) (cross((x1)-(x0),(y1)-(y0),(x2)-(x0),(y2)-(y0)))
8 int main()
9 {
10 int n;
11 while(scanf("%d",&n)!=EOF&&n)
12 {
13 int i;
14
15 double x[3],y[3],aera=0;
16 scanf("%lf%lf",&x[2],&y[2]);
17 for(i=1;i<n;i++)
18 {
19 scanf("%lf%lf",&x[i%2],&y[i%2]);
20 if(i>1) aera+=get_aera(x[2],y[2],x[(i+1)%2],y[(i+1)%2],x[i%2],y[i%2]);
21 }
22 aera*=0.5;
23 if(aera<0) aera=-aera;
24 printf("%.0f\n",aera+1e-8);
25
26 }
27 return 0;
28 }
]]>
2銆丄-C-B錛岃繖縐嶆儏鍐佃冭檻婕忎簡錛屽氨鏄氳繃C榪欎釜綰挎妸淇╀釜涓嶈繛閫氱殑闆嗗悎緇欐墦閫氫簡
鍏蜂綋浠ｇ爜搴旇鏄繖鏍?br />for(int j=0;j<now;j++)
if(find(now)!=find(j)&&cross(now,j))
set[find(now)]=find(j);
寮濮嬬硦娑傝泲鐨勫啓鎴愪簡
for(int j=0;j<now;j++)
if(cross(now,j))
set[now]=find(j),break;
榪欎釜灝辨槸鍙冭檻浜嗙涓縐嶆儏鍐點?br />
鍏充簬鏁板瓧璇嗗埆鐨勯棶棰樺氨濂藉姙澶氫簡錛屼富瑕佹牴鎹儴鍒嗙浉浜ゅ拰鐐圭浉浜ょ殑鏁扮洰浠ュ強鑱旈氶泦涓嚎孌電殑鏁扮洰鏉ュ垽鏂暟瀛楋紙5鍜?榪樿鏍規嵁鍙夌Н鍐嶆潵寮勪笅錛夛紝榪欓鍙楃泭鏈娣辯殑灝辨槸騫舵煡闆嗛偅閲岋紝瀹規槗鐘殑閿欒銆?br />
浠ｇ爜濡備笅錛?br />
1 Source Code
2
3 Problem: 3943 User: yzhw
4 Memory: 656K Time: 188MS
5 Language: G++ Result: Accepted
6 Source Code
7 # include <cstdio>
8 # include <vector>
9 # include <cstring>
10 # include <map>
11 using namespace std;
12 # define N 1005
13 # define min(a,b) ((a)<(b)?(a):(b))
14 # define max(a,b) ((a)>(b)?(a):(b))
15 struct line
16 {
17 int x1,y1,x2,y2;
18 }l[N];
19 bool in(int x,int y,const line &pos)
20 {
21 if(x>=min(pos.x1,pos.x2)&&x<=max(pos.x1,pos.x2)&&
22 y>=min(pos.y1,pos.y2)&&y<=max(pos.y1,pos.y2)&&
23 (pos.y2-pos.y1)*(pos.x2-x)==(pos.x2-pos.x1)*(pos.y2-y))
24 return true;
25 else return false;
26 }
27 int cross(const line &a,const line &b)
28 {
29 if(a.x1==b.x1&&a.y1==b.y1||
30 a.x2==b.x1&&a.y2==b.y1||
31 a.x1==b.x2&&a.y1==b.y2||
32 a.x2==b.x2&&a.y2==b.y2) return 1;
33 else if(in(a.x1,a.y1,b)||in(a.x2,a.y2,b)||in(b.x1,b.y1,a)||in(b.x2,b.y2,a)) return 2;
34 else return 0;
35 }
36 int cross(int x1,int y1,int x2,int y2)
37 {
38 return x1*y2-x2*y1;
39 }
40 struct node
41 {
42 vector<line> data;
43 int type() const
44 {
45 int num[3]={0,0,0};
46 for(int i=0;i<data.size();i++)
47 for(int j=i+1;j<data.size();j++)
48 num[cross(data[i],data[j])]++;
49 if(num[1]==4&&num[2]==0)
50 {
51 if(data.size()==4) return 0;
52 else
53 {
54 int target=-1,x1,y1,x2,y2;
55 for(int i=0;i<data.size();i++)
56 {
57 bool flag=true;
58 for(int j=0;j<data.size()&&flag;j++)
59 if(j!=i&&(data[i].x1==data[j].x1&&data[i].y1==data[j].y1||data[i].x1==data[j].x2&&data[i].y1==data[j].y2))
60 flag=false;
61 if(flag)
62 {
63 target=i;
64 x1=data[i].x2,y1=data[i].y2;
65 x2=data[i].x1,y2=data[i].y1;
66 break;
67 }
68 flag=true;
69 for(int j=0;j<data.size()&&flag;j++)
70 if(j!=i&&(data[i].x2==data[j].x1&&data[i].y2==data[j].y1||data[i].x2==data[j].x2&&data[i].y2==data[j].y2))
71 flag=false;
72 if(flag)
73 {
74 target=i;
75 x1=data[i].x1,y1=data[i].y1;
76 x2=data[i].x2,y2=data[i].y2;
77 break;
78 }
79 }
80 for(int i=0;i<data.size();i++)
81 if(i!=target)
82 {
83 if(data[i].x1==x1&&data[i].y1==y1)
84 return cross(data[i].x2-data[i].x1,data[i].y2-data[i].y1,x1-x2,y1-y2)<0?5:2;
85 else if(data[i].x2==x1&&data[i].y2==y1)
86 return cross(data[i].x1-data[i].x2,data[i].y1-data[i].y2,x1-x2,y1-y2)<0?5:2;
87 }
88 }
89 printf("wa!\n");
90 while(true);
91 }
92 else if(num[1]==0&&num[2]==0)
93 return 1;
94 else if(num[1]==4&&num[2]==0)
95 return 2;
96 else if(num[1]==2&&num[2]==1)
97 return 3;
98 else if(num[1]==1&&num[2]==1)
99 return 4;
100 else if(num[1]==4&&num[2]==1)
101 return 6;
102 else if(num[1]==2&&num[2]==0)
103 return 7;
104 else if(num[1]==4&&num[2]==2)
105 return 8;
106 else if(num[1]==3&&num[2]==1)
107 return 9;
108 }
109 };
110 map<int,node> data;
111 int n,set[N],ans[10];
112 int find(int pos)
113 {
114 if(set[pos]==pos) return pos;
115 else return set[pos]=find(set[pos]);
116 }
117 int main()
118 {
119 while(scanf("%d",&n)!=EOF&&n)
120 {
121 data.clear();
122 memset(ans,0,sizeof(ans));
123 for(int i=0;i<n;i++)
124 {
125 set[i]=i;
126 scanf("%d%d%d%d",&l[i].x1,&l[i].y1,&l[i].x2,&l[i].y2);
127 for(int j=0;j<i;j++)
128 if(cross(l[i],l[j])&&find(i)!=find(j))
129 set[find(i)]=find(j);
130 }
131 for(int i=0;i<n;i++)
132 data[find(i)].data.push_back(l[i]);
133 for(map<int,node>::iterator i=data.begin();i!=data.end();i++)
134 ans[i->second.type()]++;
135 printf("%d",ans[0]);
136 for(int i=1;i<10;i++)
137 printf(" %d",ans[i]);
138 printf("\n");
139 }
140 return 0;
141 }
2
3 Problem: 3943 User: yzhw
4 Memory: 656K Time: 188MS
5 Language: G++ Result: Accepted
6 Source Code
7 # include <cstdio>
8 # include <vector>
9 # include <cstring>
10 # include <map>
11 using namespace std;
12 # define N 1005
13 # define min(a,b) ((a)<(b)?(a):(b))
14 # define max(a,b) ((a)>(b)?(a):(b))
15 struct line
16 {
17 int x1,y1,x2,y2;
18 }l[N];
19 bool in(int x,int y,const line &pos)
20 {
21 if(x>=min(pos.x1,pos.x2)&&x<=max(pos.x1,pos.x2)&&
22 y>=min(pos.y1,pos.y2)&&y<=max(pos.y1,pos.y2)&&
23 (pos.y2-pos.y1)*(pos.x2-x)==(pos.x2-pos.x1)*(pos.y2-y))
24 return true;
25 else return false;
26 }
27 int cross(const line &a,const line &b)
28 {
29 if(a.x1==b.x1&&a.y1==b.y1||
30 a.x2==b.x1&&a.y2==b.y1||
31 a.x1==b.x2&&a.y1==b.y2||
32 a.x2==b.x2&&a.y2==b.y2) return 1;
33 else if(in(a.x1,a.y1,b)||in(a.x2,a.y2,b)||in(b.x1,b.y1,a)||in(b.x2,b.y2,a)) return 2;
34 else return 0;
35 }
36 int cross(int x1,int y1,int x2,int y2)
37 {
38 return x1*y2-x2*y1;
39 }
40 struct node
41 {
42 vector<line> data;
43 int type() const
44 {
45 int num[3]={0,0,0};
46 for(int i=0;i<data.size();i++)
47 for(int j=i+1;j<data.size();j++)
48 num[cross(data[i],data[j])]++;
49 if(num[1]==4&&num[2]==0)
50 {
51 if(data.size()==4) return 0;
52 else
53 {
54 int target=-1,x1,y1,x2,y2;
55 for(int i=0;i<data.size();i++)
56 {
57 bool flag=true;
58 for(int j=0;j<data.size()&&flag;j++)
59 if(j!=i&&(data[i].x1==data[j].x1&&data[i].y1==data[j].y1||data[i].x1==data[j].x2&&data[i].y1==data[j].y2))
60 flag=false;
61 if(flag)
62 {
63 target=i;
64 x1=data[i].x2,y1=data[i].y2;
65 x2=data[i].x1,y2=data[i].y1;
66 break;
67 }
68 flag=true;
69 for(int j=0;j<data.size()&&flag;j++)
70 if(j!=i&&(data[i].x2==data[j].x1&&data[i].y2==data[j].y1||data[i].x2==data[j].x2&&data[i].y2==data[j].y2))
71 flag=false;
72 if(flag)
73 {
74 target=i;
75 x1=data[i].x1,y1=data[i].y1;
76 x2=data[i].x2,y2=data[i].y2;
77 break;
78 }
79 }
80 for(int i=0;i<data.size();i++)
81 if(i!=target)
82 {
83 if(data[i].x1==x1&&data[i].y1==y1)
84 return cross(data[i].x2-data[i].x1,data[i].y2-data[i].y1,x1-x2,y1-y2)<0?5:2;
85 else if(data[i].x2==x1&&data[i].y2==y1)
86 return cross(data[i].x1-data[i].x2,data[i].y1-data[i].y2,x1-x2,y1-y2)<0?5:2;
87 }
88 }
89 printf("wa!\n");
90 while(true);
91 }
92 else if(num[1]==0&&num[2]==0)
93 return 1;
94 else if(num[1]==4&&num[2]==0)
95 return 2;
96 else if(num[1]==2&&num[2]==1)
97 return 3;
98 else if(num[1]==1&&num[2]==1)
99 return 4;
100 else if(num[1]==4&&num[2]==1)
101 return 6;
102 else if(num[1]==2&&num[2]==0)
103 return 7;
104 else if(num[1]==4&&num[2]==2)
105 return 8;
106 else if(num[1]==3&&num[2]==1)
107 return 9;
108 }
109 };
110 map<int,node> data;
111 int n,set[N],ans[10];
112 int find(int pos)
113 {
114 if(set[pos]==pos) return pos;
115 else return set[pos]=find(set[pos]);
116 }
117 int main()
118 {
119 while(scanf("%d",&n)!=EOF&&n)
120 {
121 data.clear();
122 memset(ans,0,sizeof(ans));
123 for(int i=0;i<n;i++)
124 {
125 set[i]=i;
126 scanf("%d%d%d%d",&l[i].x1,&l[i].y1,&l[i].x2,&l[i].y2);
127 for(int j=0;j<i;j++)
128 if(cross(l[i],l[j])&&find(i)!=find(j))
129 set[find(i)]=find(j);
130 }
131 for(int i=0;i<n;i++)
132 data[find(i)].data.push_back(l[i]);
133 for(map<int,node>::iterator i=data.begin();i!=data.end();i++)
134 ans[i->second.type()]++;
135 printf("%d",ans[0]);
136 for(int i=1;i<10;i++)
137 printf(" %d",ans[i]);
138 printf("\n");
139 }
140 return 0;
141 }
]]>
]]>
錛?img src="http://acm.hdu.edu.cn/data/images/3682-1.gif" alt="" />
寮濮嬪啓鐨勬椂鍊欏嚭鐜頒釜BUG錛屾棤濂堬紝涓婄綉鎵鵑瑙ｏ紝鏇存棤濂堬紝閮芥槸浜涘嚑鍙ヨ瘽hash鐒跺悗灝辨槸涓鍫嗛毦鎳傜殑浠ｇ爜銆傘?br />鍚庢潵浠旂粏鎯充簡鎯籌紝鎶婇噸澶嶇殑鎿嶄綔鍘婚櫎鍚庯紙灝辨槸涓ゆ鍒犻櫎鐨勫悓涓涓湪鏉★級錛屼笅闈㈠氨鏄釜寰堢畝鍗曠殑瀹規枼鍘熺悊浜?br />鍥犱負鍘婚櫎浜嗛噸澶嶆搷浣滐紝涓涓湪鍧楁渶澶氳鍒犻櫎3嬈★紝鐒跺悗鍒犻櫎鐨勪釜鏁板氨涓鴻鍒犻櫎鑷沖皯涓嬈＄殑涓暟-鍒犻櫎鑷沖皯涓ゆ鐨勪釜鏁?鍒犻櫎鑷沖皯3嬈＄殑涓暟銆備笉鑳藉己琛屾灇涓撅紝鍙互鐢╩ap鎴栬呬紶璇翠腑鐨刪ash璁板綍琚垹闄ゆ帀鏈ㄥ潡鐨勬鏁般傝繖閲岋紝鐢變簬鎿嶄綔鏈澶歮=1000錛屽垹闄ゆ湪鍧楁暟鏈澶氫負C(m,2)錛岀劧鍚庝袱涓ゆ灇涓炬搷浣滐紝鎶婄浉浜ゆ湪鍧楀垹闄ゆ鏁?1錛岀劧鍚庢渶鍚巑ap涓墍鏈夋湪鍧楀垹闄ゆ鏁板彧鑳芥湁2涓鹼細1鍜?錛屽綋鍊間負1鏃訛紝total-1,鍊間負3鏃訛紝total-2
涓轟粈涔堬紵鍥犱負鎴戣浜嗭紝涓涓湪鍧楁渶澶氳鍒犻櫎3嬈★紝鐒跺悗淇╀咯鏋氫婦鐨勬椂鍊欙紝浣犳噦鐨勩?br />
1 # include <cstdio>
2 # include <utility>
3 # include <cstring>
4 # include <algorithm>
5 # include <functional>
6 # include <set>
7 # include <cstdlib>
8 # include <map>
9 using namespace std;
10 struct node
11 {
12 int p[3];
13 bool operator<(const node &pos) const
14 {
15 for(int i=0;i<3;i++)
16 if(p[i]!=pos.p[i])
17 return p[i]<pos.p[i];
18 return false;
19 }
20 };
21 pair<int,int> data[1000][2];
22 set<pair<pair<int,int>,pair<int,int> > > r1;
23 map<node,int> r2;
24 int main()
25 {
26 int test;
27 scanf("%d",&test);
28 while(test--)
29 {
30 int n,m,p=0;
31 char str[128];
32 scanf("%d%d",&n,&m);
33 r1.clear();r2.clear();
34 while(m--)
35 {
36 scanf("%s",str);
37 char *t=strtok(str,",");
38 data[p][0].first=(*t)-'X';
39 data[p][0].second=atoi(t+2);
40 t=strtok(NULL," ");
41 data[p][1].first=(*t)-'X';
42 data[p][1].second=atoi(t+2);
43 if(data[p][0].first>data[p][1].first) swap(data[p][0],data[p][1]);
44 pair< pair<int,int>,pair<int,int> > tt;
45 tt.first=data[p][0];
46 tt.second=data[p][1];
47 if(data[p][0].second>=1&&data[p][0].second<=n&&data[p][1].second>=1&&data[p][1].second<=n&&r1.find(tt)==r1.end()) p++,r1.insert(tt);
48 }
49 m=p;
50 for(int i=0;i<m;i++)
51 for(int j=i+1;j<m;j++)
52 if(data[i][0]==data[j][0]&&data[i][1].first!=data[j][1].first||
53 data[i][1]==data[j][0]&&data[i][0].first!=data[j][1].first||
54 data[i][0]==data[j][1]&&data[i][1].first!=data[j][0].first||
55 data[i][1]==data[j][1]&&data[i][0].first!=data[j][0].first)
56 {
57 node t;
58 t.p[data[i][0].first]=data[i][0].second;
59 t.p[data[i][1].first]=data[i][1].second;
60 t.p[data[j][0].first]=data[j][0].second;
61 t.p[data[j][1].first]=data[j][1].second;
62 r2[t]++;
63 }
64 int total=m*n;
65 for(map<node,int>::iterator i=r2.begin();i!=r2.end();i++)
66 if(i->second==1) total--;
67 else total-=2;
68 printf("%d\n",total);
69 }
70 //system("pause");
71 return 0;
72 }
73
2 # include <utility>
3 # include <cstring>
4 # include <algorithm>
5 # include <functional>
6 # include <set>
7 # include <cstdlib>
8 # include <map>
9 using namespace std;
10 struct node
11 {
12 int p[3];
13 bool operator<(const node &pos) const
14 {
15 for(int i=0;i<3;i++)
16 if(p[i]!=pos.p[i])
17 return p[i]<pos.p[i];
18 return false;
19 }
20 };
21 pair<int,int> data[1000][2];
22 set<pair<pair<int,int>,pair<int,int> > > r1;
23 map<node,int> r2;
24 int main()
25 {
26 int test;
27 scanf("%d",&test);
28 while(test--)
29 {
30 int n,m,p=0;
31 char str[128];
32 scanf("%d%d",&n,&m);
33 r1.clear();r2.clear();
34 while(m--)
35 {
36 scanf("%s",str);
37 char *t=strtok(str,",");
38 data[p][0].first=(*t)-'X';
39 data[p][0].second=atoi(t+2);
40 t=strtok(NULL," ");
41 data[p][1].first=(*t)-'X';
42 data[p][1].second=atoi(t+2);
43 if(data[p][0].first>data[p][1].first) swap(data[p][0],data[p][1]);
44 pair< pair<int,int>,pair<int,int> > tt;
45 tt.first=data[p][0];
46 tt.second=data[p][1];
47 if(data[p][0].second>=1&&data[p][0].second<=n&&data[p][1].second>=1&&data[p][1].second<=n&&r1.find(tt)==r1.end()) p++,r1.insert(tt);
48 }
49 m=p;
50 for(int i=0;i<m;i++)
51 for(int j=i+1;j<m;j++)
52 if(data[i][0]==data[j][0]&&data[i][1].first!=data[j][1].first||
53 data[i][1]==data[j][0]&&data[i][0].first!=data[j][1].first||
54 data[i][0]==data[j][1]&&data[i][1].first!=data[j][0].first||
55 data[i][1]==data[j][1]&&data[i][0].first!=data[j][0].first)
56 {
57 node t;
58 t.p[data[i][0].first]=data[i][0].second;
59 t.p[data[i][1].first]=data[i][1].second;
60 t.p[data[j][0].first]=data[j][0].second;
61 t.p[data[j][1].first]=data[j][1].second;
62 r2[t]++;
63 }
64 int total=m*n;
65 for(map<node,int>::iterator i=r2.begin();i!=r2.end();i++)
66 if(i->second==1) total--;
67 else total-=2;
68 printf("%d\n",total);
69 }
70 //system("pause");
71 return 0;
72 }
73
]]>
]]>
1銆佹彃鍏?br />鎸夌収鍒掑垎鏍戠殑瀹氫箟錛屽鏋滃皬浜庢湁搴忚〃涓腑闂磋妭鐐圭殑鍊鹼紝灝遍掑綊鎻掑叆宸﹀瓙鏍戯紝鍚﹀垯閫掑綊鎻掑叆鍙沖瓙鏍戙傛洿鏂板綋鍓嶅尯闂存鐨勫垝鍒嗕俊鎭紙鏃犻潪灝辨槸寰鍚庤綆椾竴涓級
2銆佽闂畇,e鍖洪棿絎琸灝忔暟
鏌ヨs,e鍖洪棿閲岄潰鍒掑垎鍒板乏瀛愭爲鐨勪釜鏁癷錛屽鏋渋>=k錛岄偅涔堟樉鐒墮掑綊鍒板乏瀛愭爲鏌ヨ錛屽惁鍒欏氨鏄掑綊鍒板彸瀛愭爲鏌ヨk-i灝忕殑鏁般傛敞鎰忥紒榪欓噷瑕侀噸鏂板畾浣嶅乏瀛愭爲鍜屽彸瀛愭爲涓殑鍖洪棿錛岀敱浜庢槸闂尯闂達紝閭ｄ箞鍋氱鐐逛負s+sum(s-1),鍙崇鐐逛負s+sum(e)-1錛岃繖涓噺涓涓簡銆傘傝皟浜嗘垜鍗婂ぉ銆傘傚搸銆傘備互鍓嶅啓閮芥槸宸﹂棴鍙沖紑鍖洪棿鐨勶紝緇撴灉涔犳儻浜嗐傘?br />3銆佹煡璇㈠間負k鐨勬暟鐨勪綅嬈?br />榪欎釜闇瑕佷竴涓緟鍔╂暟緇勶紝璁板綍鍊間負k鐨勬暟鎻掑湪鏈欏跺眰鍖洪棿鐨勫摢涓綅緗簡銆傝繖涓姙濂藉悗錛屽氨瀹規槗浜嗭紝濡傛灉鏁拌鍒掑垎鍒頒簡宸﹀瓙鏍戯紝閭ｄ箞閫掑綊鏌ヨ宸﹀瓙鏍戯紝鍚﹀垯榪斿洖閫掑綊鏌ヨ鍙沖瓙鏍戠殑鍊煎姞涓婂綋鍓嶅尯闂磋鍒掑垎鍒板乏瀛愭爲鐨勪釜鏁?br />4銆佹煡璇ank k鐨勬暟
鍚屾牱鏄繖鏍鳳紝濡傛灉褰撳墠鍖洪棿琚垝鍒嗗埌宸﹀瓙鏍戠殑涓暟灝忎簬絳変簬k錛岄偅涔堥掑綊鏌ヨ宸﹀瓙鏍戯紝鍚﹀垯閫掑綊鏌ヨ鍙沖瓙鏍戜腑rank涓簁-宸﹀瓙鏍戠殑size銆?br />澶ф鎬濇兂灝辨槸榪欐牱浜嗭紝瀹炵幇鏈夊緢澶氱粏鑺傦紝姣斿璇村亣璁緋==鍖洪棿宸︾鐐癸紙宸﹀尯闂存湪鏈夋暟錛夛紝閭ｄ箞綆梥um(p-1)鐨勬椂鍊欏氨瑕佺壒鍒や笅浜嗐傛垜鍠滄鐢ㄤ笁鍏冨紡錛屽緢鏂逛究銆?br />
浠ｇ爜
# include <cstdio>
# include <cstring>
# include <map>
using namespace std;
# define N 100005
int arr[20][N];
struct node
{
int s,e,layer;
int c;
}st[4*N];
int q[500000][4],c;
int remap[N],position[N];
map<int,int> refer;
void init(int s,int e,int layer,int pos=1)
{
st[pos].s=s;st[pos].e=e;
st[pos].layer=layer;
st[pos].c=st[pos].s;
if(s!=e) init(s,(s+e)/2,layer+1,pos<<1),init((s+e)/2+1,e,layer+1,(pos<<1)+1);
}
void insert(int value,int pos=1)
{
if(st[pos].s==st[pos].e)
arr[st[pos].layer][st[pos].c++]=value;
else
{
if(value<=(st[pos].s+st[pos].e)/2)
{
arr[st[pos].layer][st[pos].c]=(st[pos].c==st[pos].s?0:arr[st[pos].layer][st[pos].c-1])+1;
st[pos].c++;
insert(value,pos<<1);
}
else
{
arr[st[pos].layer][st[pos].c]=(st[pos].c==st[pos].s?0:arr[st[pos].layer][st[pos].c-1]);
st[pos].c++;
insert(value,(pos<<1)+1);
}
}
}
int q1(int s,int t,int k,int pos=1)
{
if(st[pos].s==st[pos].e)
return remap[arr[st[pos].layer][st[pos].s]];
else
{
if(arr[st[pos].layer][t]-(s==st[pos].s?0:arr[st[pos].layer][s-1])>=k)//left
return q1(st[pos].s+(s==st[pos].s?0:arr[st[pos].layer][s-1]),st[pos].s+arr[st[pos].layer][t]-1,k,pos<<1);
else//right
{
k-=arr[st[pos].layer][t]-(s==st[pos].s?0:arr[st[pos].layer][s-1]);
return q1((st[pos].s+st[pos].e)/2+1+s-1-st[pos].s+1-(s==st[pos].s?0:arr[st[pos].layer][s-1]),(st[pos].s+st[pos].e)/2+1+t-st[pos].s+1-arr[st[pos].layer][t]-1,k,(pos<<1)+1);
}
}
}
int q2(int s,int pos=1)
{
if(st[pos].s==st[pos].e) return 1;
else if(arr[st[pos].layer][s]-(s==st[pos].s?0:arr[st[pos].layer][s-1]))
return q2(st[pos].s+arr[st[pos].layer][s]-1,pos<<1);
else
return (st[pos].c==st[pos].s?0:arr[st[pos].layer][st[pos].c-1])+q2((st[pos].s+st[pos].e)/2+1+s-st[pos].s+1-arr[st[pos].layer][s]-1,(pos<<1)+1);
}
int q3(int k,int pos=1)
{
if(st[pos].s==st[pos].e) return remap[arr[st[pos].layer][st[pos].s]];
else if(k<=(st[pos].c==st[pos].s?0:arr[st[pos].layer][st[pos].c-1])) return q3(k,pos<<1);
else return q3(k-(st[pos].s==st[pos].c?0:arr[st[pos].layer][st[pos].c-1]),(pos<<1)+1);
}
int main()
{
int n,test=1;
while(scanf("%d",&n)!=EOF)
{
refer.clear();c=1;
memset(arr,0,sizeof(arr));
for(int i=0;i<n;i++)
{
char tmp[12];
scanf("%s",tmp);
if(*tmp=='I')
q[i][0]=0;
else q[i][0]=tmp[6]-48;
switch(q[i][0])
{
case 0:
scanf("%d",&q[i][1]);
refer[q[i][1]]=0;
break;
case 1:
scanf("%d%d%d",&q[i][1],&q[i][2],&q[i][3]);
break;
default:
scanf("%d",&q[i][1]);
break;
};
}
for(map<int,int>::iterator i=refer.begin();i!=refer.end();i++)
remap[c]=i->first,i->second=c++;
init(1,c-1,0);
long long t[4]={0,0,0,0};
int now=1;
for(int i=0;i<n;i++)
switch(q[i][0])
{
case 0:
insert(refer[q[i][1]]);
position[refer[q[i][1]]]=now++;
break;
case 1:
t[1]+=q1(q[i][1],q[i][2],q[i][3]);
break;
case 2:
t[2]+=q2(position[refer[q[i][1]]]);
break;
case 3:
t[3]+=q3(q[i][1]);
break;
};
printf("Case %d:\n%I64d\n%I64d\n%I64d\n",test++,t[1],t[2],t[3]);
}
return 0;
}
]]>