預計分數：T1：40AC+60TLE T2：40AC+60TLE T3：10AC+90TLE 總分=90 實際分數：T1：100AC+0TLE T2：80AC+20TLE T3：20AC+80TLE 總分=200 感想：數據水的一逼！！ 題目實際難度: T1:提高/提高+ T2:提高+ T3:提高+ ...
預計分數：T1：40AC+60TLE
T2：40AC+60TLE
T3：10AC+90TLE
總分=90
實際分數：T1：100AC+0TLE
T2：80AC+20TLE
T3：20AC+80TLE
總分=200
感想：數據水的一逼！！
題目實際難度:
T1:提高/提高+
T2:提高+
T3:提高+/省選-
我眼中的難度
T1:普及
T2:普及-
T3:入門難度
2039. 樹的統計
★★ 輸入文件：counttree.in 輸出文件：counttree.out 簡單對比
時間限制：1 s
記憶體限制：128 MB
【題目描述】
-
關於樹的統計問題有多種多樣的版本，這裡你需要解決一個比較簡單的問題：對於一棵包含N個節點的有根樹，將所有點從1到N編號後，對於每一個節點v，統計出以v為根的子樹中有多少個點的編號比v小。
【輸入格式】
輸入第一行包含一個整數N，以下N行每行包含一個整數，其中第i行的整數表示編號為i的節點的父親節點的編號，根的父親節點編號為0。
【輸出格式】
輸出包含N行，其中第i行給出編號為i的節點的統計結果。
【樣例輸入】
3 2 3 0
【樣例輸出】
0 1 2
【提示】
在此鍵入。
【來源】
20%的數據1<=n<=1000
100%的數據1<=n<=100000
上來看了一眼題目難度是兩顆黑星，感覺十分不可做（因為我一般在cogs刷兩星的題目很少一遍不看題解AC）
一開始以為是樹上倍增.樹上DP.RMQ之類的，但是都不會啊。。
無奈只能暴力。
暴力思路：
一：讀入每一個點，記錄他的father，
二：枚舉每一個點，如果他的father不為0且它的father的值比他大，那麼它的father的值就++
正解：
DFS序+樹狀數組
但是看了一下評測記錄我的暴力0.125s秒殺所有正解+暴力=.=
1 #include<iostream> 2 #include<cstdio> 3 #include<cstring> 4 #include<cmath> 5 using namespace std; 6 const int MAXN=100001; 7 int read(int & n) 8 { 9 char c='/';int x=0,flag=0; 10 while(c<'0'||c>'9') 11 {c=getchar(); 12 if(c=='-')flag=1;} 13 while(c>='0'&&c<='9') 14 {x=x*10+c-48;c=getchar();} 15 if(flag)n=-x; 16 else n=x; 17 return n; 18 } 19 int n,p; 20 int fa[MAXN]; 21 int ch[MAXN]; 22 int num[MAXN]; 23 int main() 24 { 25 freopen("counttree.in","r",stdin); 26 freopen("counttree.out","w",stdout); 27 read(n); 28 for(int i=1;i<=n;i++) 29 { 30 read(p); 31 fa[i]=p; 32 } 33 for(int i=1;i<=n;i++) 34 { 35 int p=i; 36 while(fa[p]!=0) 37 { 38 if(fa[p]>i) 39 num[fa[p]]++; 40 p=fa[p]; 41 } 42 } 43 for(int i=1;i<=n;i++) 44 { 45 printf("%d ",num[i]); 46 } 47 return 0; 48 }
1682. [HAOI2014]貼海報
★★☆ 輸入文件：ha14d.in 輸出文件：ha14d.out 簡單對比
時間限制：1 s
記憶體限制：256 MB
【題目描述】
Bytetown城市要進行市長競選，所有的選民可以暢所欲言地對競選市長的候選人發表言論。為了統一管理，城市委員會為選民準備了一個張貼海報的electoral牆。
張貼規則如下：
1．electoral牆是一個長度為N個單位的長方形，每個單位記為一個格子；
2．所有張貼的海報的高度必須與electoral牆的高度一致的；
3．每張海報以“A B”表示，即從第A個格子到第B個格子張貼海報；
4．後貼的海報可以覆蓋前面已貼的海報或部分海報。
現在請你判斷，張貼完所有海報後，在electoral牆上還可以看見多少張海報。
【輸入格式】
第一行： N M 分別表示electoral牆的長度和海報個數
接下來M行: Ai Bi 表示每張海報張貼的位置
【輸出格式】
輸出貼完所有海報後，在electoral牆上還可以看見的海報數。
【樣例輸入】
100 5
1 4
2 6
8 10
3 4
7 10
【樣例輸出】
4
【提示】
【約束條件】
1 0<= N <= 10000000 1<=M<=1000 1<= Ai <= Bi <=10000000
所有的數據都是整數。數據之間有一個空格
上來看了一眼立馬用10min打出了暴力，打完T3的暴力之後回來看了一下這個題感覺是線段樹的裸體
然後用15min寫出了線段樹
但是！！！
線段樹！！
居然！！
比！！
暴力！！
慢！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！
而且！！
還！！
爆記憶體！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！
這就比較尷尬了，望著對拍程式上每次都是暴力先跑完然後線段樹等一秒再出結果的場景，我還能說什麼、、
難道是因為我寫的線段樹太醜了？？？
=.=
暴力思路：模擬張貼每一個海報
1 #include<iostream> 2 #include<cstdio> 3 #include<cstring> 4 #include<cmath> 5 using namespace std; 6 const int MAXN=10000001; 7 int n,m,x,y; 8 int read(int & n) 9 { 10 char c='/';int x=0,flag=0; 11 while(c<'0'||c>'9') 12 {c=getchar(); 13 if(c=='-')flag=1;} 14 while(c>='0'&&c<='9') 15 {x=x*10+c-48;c=getchar();} 16 if(flag)n=-x; 17 else n=x; 18 return n; 19 } 20 int a[MAXN]; 21 int vis[MAXN]; 22 int now=1; 23 int ans=0; 24 int main() 25 { 26 freopen("a.in","r",stdin); 27 freopen("b.out","w",stdout); 28 read(n);read(m); 29 for(int i=1;i<=m;i++) 30 { 31 read(x);read(y); 32 if(x>y)swap(x,y); 33 for(int j=x;j<=y;j++) 34 a[j]=i; 35 } 36 for(int i=1;i<=n;i++) 37 { 38 if(vis[a[i]]==0&&a[i]!=0) 39 { 40 ans++; 41 vis[a[i]]=1; 42 } 43 } 44 printf("%d",ans); 45 return 0; 46 }暴力80
正解：老師講了個掃描線但是沒聽懂啊，，，，，so參考了題解的浮水法
首先我們讀入每一個海報的l和r，
然後逆序掃描，預設ans為一，因為最後的一張一定能看見
對於每一個i一直向上枚舉，就像浮水一樣，如果經過不斷的裁剪之後能夠>n的話
ans++
1 #include<iostream> 2 #include<cstdio> 3 #include<cstring> 4 #include<cmath> 5 #include<algorithm> 6 using namespace std; 7 const int MAXN=1001; 8 int n,m,ans=1; 9 int vis[MAXN]; 10 struct node 11 { 12 int l; 13 int r; 14 int id; 15 }a[MAXN]; 16 int read(int & n) 17 { 18 char c='/';int flag=0,x=0; 19 while(c<'0'||c>'9') 20 {if(c=='-')flag=1; 21 c=getchar();} 22 while(c>='0'&&c<='9') 23 {x=x*10+(c-48); 24 c=getchar();} 25 if(flag)n=-x; 26 else n=x; 27 } 28 void water(int ll,int rr,int now,int pos) 29 { 30 if(vis[pos]) 31 return ; 32 while(now<=m&&(rr<=a[now].l||ll>=a[now].r)) 33 now++; 34 if(now>m) 35 { 36 vis[pos]=1; 37 ans++; 38 return ; 39 } 40 if(ll<a[now].l&&rr>a[now].l) 41 water(ll,a[now].l,now+1,pos); 42 if(rr>a[now].r&&ll<a[now].r) 43 water(a[now].r,rr,now+1,pos); 44 45 } 46 int main() 47 { 48 freopen("ha14d.in","r",stdin); 49 freopen("ha14d.out","w",stdout); 50 read(n);read(m); 51 for(int i=1;i<=m;i++) 52 { 53 read(a[i].l); 54 read(a[i].r); 55 a[i].r=a[i].r+1; 56 a[i].id=i; 57 } 58 for(int i=m-1;i>=1;i--) 59 { 60 water(a[i].l,a[i].r,i+1,i); 61 } 62 printf("%d",ans); 63 return 0; 64 }浮水法秒AC
1619. [HEOI2012]採花
★★☆ 輸入文件：1flower.in 輸出文件：1flower.out 簡單對比
時間限制：5 s
記憶體限制：128 MB
【題目描述】
蕭薰兒是古國的公主，平時的一大愛好是採花。 今天天氣晴朗，陽光明媚，公主清晨便去了皇宮中新建的花園採花。花園足夠大，容納了n朵花，花有c種顏色（用整數1-c表示），且花是排成一排的，以便於公主採花。公主每次採花後會統計採到的花的顏色數，顏色數越多她會越高興！同時，她有一癖好，她不允許最後自己採到的花中，某一顏色的花只有一朵。為此，公主每採一朵花，要麼此前已採到此顏色的花，要麼有相當正確的直覺告訴她，她必能再次採到此顏色的花。由於時間關係，公主只能走過花園連續的一段進行採花，便讓女僕福涵潔安排行程。福涵潔綜合各種因素擬定了m個行程，然後一一向你詢問公主能採到多少朵花（她知道你是編程高手，定能快速給出答案！），最後會選擇令公主最高興的行程（為了拿到更多獎金！）。【輸入格式】
【輸出格式】
共m行，每行一個整數，第i個數表示公主在女僕的第i個行程中能採到的花的顏色數。【樣例輸入】
5 3 5 1 2 2 3 1 1 5 1 2 2 2 2 3 3 5
【樣例輸出】
2 0 0 1 0 【樣例說明】 詢問[1, 5]：公主採顏色為1和2的花，由於顏色3的花只有一朵，公主不採；詢問[1, 2]：顏色1和顏色2的花均只有一朵，公主不採； 詢問[2, 2]：顏色2的花只有一朵，公主不採； 詢問[2, 3]：由於顏色2的花有兩朵，公主採顏色2的花； 詢問[3, 5]：顏色1、2、3的花各一朵，公主不採。
【提示】
【數據範圍】
對於100%的數據，1 ≤ n ≤ 10^6，c ≤ n，m ≤10^6。
【來源】
【題目來源】
一開始以為這題是線段樹，，後來發現線段樹好像沒有這個功能
然後就想莫隊，看了看時間發現還有一個半小時，以為這道題做不出來了，就打了個暴力去做T2
臨收捲還有二十分鐘左右的時候老師說T3莫隊20分，（後來我用莫隊AC了，，，實力打臉）
暴力思路：暴力
1 #include<iostream> 2 #include<cstdio> 3 #include<cstring> 4 #include<cmath> 5 using namespace std; 6 const int MAXN=100001; 7 int read(int & n) 8 { 9 char c='/';int x=0,flag=0; 10 while(c<'0'||c>'9') 11 {c=getchar(); 12 if(c=='-')flag=1;} 13 while(c>='0'&&c<='9') 14 {x=x*10+c-48;c=getchar();} 15 if(flag)n=-x; 16 else n=x; 17 return n; 18 } 19 int num[MAXN];// 查詢 20 int a[MAXN];// 顏色 21 int n,fl,m,x,y,p; 22 int query(int x,int y) 23 { 24 int ans=0; 25 memset(num,0,sizeof(num)); 26 for(int i=x;i<=y;i++) 27 { 28 num[a[i]]++; 29 if(num[a[i]]==2) 30 ans++; 31 } 32 return ans; 33 } 34 int main() 35 { 36 freopen("1flower.in","r",stdin); 37 freopen("1flower.out","w",stdout); 38 read(n);read(fl);read(m); 39 for(int i=1;i<=n;i++) 40 { 41 read(p); 42 a[i]=p; 43 } 44 for(int i=1;i<=m;i++) 45 { 46 read(x);read(y); 47 printf("%d\n",query(x,y)); 48 } 49 return 0; 50 }暴力
正解:
1.裸莫隊
1 #include<iostream> 2 #include<cstdio> 3 #include<cstring> 4 #include<cmath> 5 #include<algorithm> 6 using namespace std; 7 const int MAXN=1000001; 8 int colornum[MAXN],n,color,m,a[MAXN]; 9 int base,pos[MAXN],out[MAXN]; 10 struct node 11 { 12 int l,r,id; 13 }q[MAXN]; 14 int ans=0; 15 int read(int & n) 16 { 17 char c='/';int flag=0,x=0; 18 while(c<'0'||c>'9') 19 {c=getchar();} 20 while(c>='0'&&c<='9') 21 {x=(x<<3)+(x<<1)+(c-48); 22 c=getchar();} 23 n=x; 24 } 25 inline void dele(int where) 26 { 27 if(colornum[a[where]]==2) 28 ans--; 29 colornum[a[where]]--; 30 } 31 inline void add(int where) 32 { 33 if(colornum[a[where]]==1) 34 ans++; 35 colornum[a[where]]++; 36 } 37 inline int comp(const node & a,const node & b) 38 { 39 if(pos[a.l]==pos[b.l]) 40 return a.r<b.r; 41 else return pos[a.l]<pos[b.l]; 42 } 43 inline void modui() 44 { 45 int l=1,r=0; 46 for(int i=1;i<=m;++i) 47 { 48 for(;l<q[i].l;++l) 49 dele(l); 50 for(;l>q[i].l;--l) 51 add(l-1); 52 for(;r<q[i].r;++r) 53 add(r+1); 54 for(;r>q[i].r;--r) 55 dele(r); 56 out[q[i].id]=ans; 57 } 58 } 59 int main() 60 { 61 freopen("1flower.in","r",stdin); 62 freopen("1flower.out","w",stdout); 63 read(n);read(color);read(m); 64 base=sqrt(n); 65 for(int i=1;i<=n;++i) 66 read(a[i]); 67 for(int i=1;i<=n;++i) 68 pos[i]=(i-1)/base+1; 69 for(int i=1;i<=m;++i) 70 { 71 read(q[i].l); 72 read(q[i].r); 73 q[i].id=i; 74 } 75 sort(q+1,q+m+1,comp); 76 modui(); 77 for(int i=1;i<=m;++i) 78 { 79 printf("%d\n",out[i]); 80 } 81 return 0; 82 }莫隊AC
2.因為一個顏色只有出現兩次的時候才會被採
那麼我們可以記錄這個顏色出現的位置，但這個顏色出現的次數達到兩次的時候，我們把這個區間+1
維護區間可以用樹狀數組實現
1 #include<iostream> 2 #include<cstdio> 3 #include<cstring> 4 #include<cmath> 5 #include<algorithm> 6 using namespace std; 7 const int MAXN=1000001; 8 int a[MAXN]; 9 int lb(int x) 10 {return x&-x;} 11 int read(int & n) 12 { 13 char c='/';int flag=0,x=0; 14 while(c<'0'||c>'9') 15 {if(c=='-')flag=1; 16 c=
