BZOJ3211: 花神游历各国

3211: 花神游历各国

Time Limit: 5 Sec Memory Limit: 128 MB
Submit: 817 Solved: 295
[Submit][Status]

Description

Input

Output

每次x=1时，每行一个整数，表示这次旅行的开心度

Sample Input

4

1 100 5 5

5

1 1 2

2 1 2

1 1 2

2 2 3

1 1 4

Sample Output

101

11

11

HINT

对于100%的数据， n ≤ 100000，m≤200000 ,data[i]非负且小于10^9

Source

SPOJ2713 gss4 数据已加强

题解：

花神游历各国=上帝造题的七分钟2

尼玛拿着原来的pascal就是A不了，无了奈了。。。

代码：

1.pascal

 1 var i,n,x,y,k,t,temp,m:longint;
 2     s,fa,a:array[0..200100] of int64;
 3 function find(x:longint):longint;
 4  begin
 5  if fa[x]<>x then fa[x]:=find(fa[x]);
 6  exit(fa[x]);
 7  end;
 8 function lowbit(x:longint):longint;
 9  begin
10  exit(x and (-x));
11  end;
12 procedure add(x,y:int64);
13  begin
14  while x<=n do
15   begin
16   inc(s[x],y);
17   inc(x,lowbit(x));
18   end;
19  end;
20 function sum(x:int64):int64;
21  begin
22  sum:=0;
23  while x>0 do
24   begin
25   inc(sum,s[x]);
26   dec(x,lowbit(x));
27   end;
28  exit(sum);
29  end;
30 procedure update(x,y:longint);
31  var i:longint;
32  begin
33  i:=find(x);
34  while i<=y do
35   begin
36   temp:=trunc(sqrt(a[i]));
37   add(i,temp-a[i]);
38   a[i]:=temp;
39   if a[i]=1 then fa[i]:=i+1;
40   i:=find(i+1);
41   end;
42  end;
43 procedure init;
44  begin
45  readln(n);
46  for i:=1 to n do begin read(a[i]);fa[i]:=i;add(i,a[i]);end;
47  fa[n+1]:=n+1;
48  end;
49 procedure main;
50  begin
51  readln(m);
52  for i:=1 to m do
53   begin
54   readln(k,x,y);
55   if x>y then begin t:=x;x:=y;y:=t;end;
56   case k of
57   2:update(x,y);
58   1:writeln(sum(y)-sum(x-1));
59   end;
60   end;
61  end;
62 begin
63  init;
64  main;
65 end.

View Code

pascal各种T，c++写了一遍就A了。。。

2.c++

 1 #include<cstdio>
 2 #include<cstdlib>
 3 #include<cmath>
 4 #include<cstring>
 5 #include<algorithm>
 6 #include<iostream>
 7 #include<vector>
 8 #include<map>
 9 #include<set>
10 #include<queue>
11 #define inf 1000000000
12 #define maxn 100000+100
13 #define maxm 500+100
14 #define eps 1e-10
15 #define ll long long
16 #define pa pair<int,int>
17 using namespace std;
18 inline int read()
19 {
20     int x=0,f=1;char ch=getchar();
21     while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();}
22     while(ch>='0'&&ch<='9'){x=10*x+ch-'0';ch=getchar();}
23     return x*f;
24 }
25 ll s[maxn];
26 int n,m,fa[maxn],a[maxn];
27 void add(int x,int y)
28 {
29     for(;x<=n;x+=x&(-x))s[x]+=y;
30 }
31 ll sum(int x)
32 {
33     ll t=0;
34     for(;x>0;x-=x&(-x))t+=s[x];
35     return t;
36 }
37 int find(int x){return fa[x]==x?x:fa[x]=find(fa[x]);}
38 int main()
39 {
40     freopen("input.txt","r",stdin);
41     freopen("output.txt","w",stdout);
42     n=read();
43     for(int i=1;i<=n;i++){a[i]=read();add(i,a[i]);fa[i]=i;}
44     fa[n+1]=n+1;
45     m=read();
46     while(m--)
47     {
48         int ch=read(),l=read(),r=read();//cout<<ch<<' '<<l<<' '<<r<<endl;
49         if(ch==1)printf("%lld
",sum(r)-sum(l-1));
50         else 
51         {
52             for(int i=find(l);i<=r;i=find(i+1))
53              {
54               int t=int(sqrt(a[i]));
55               add(i,t-a[i]);
56               a[i]=t;
57               if(a[i]<=1)fa[i]=find(i+1);
58              } 
59         }
60     }
61     return 0;
62 }

View Code

树状数组+并查集冲进第一版