原題：
http://172.16.0.132/senior/#contest/show/2055/1
題目描述：
很久很以前鼻忠，有一個(gè)古老的村莊——xiba村聊品，村子里生活著n+1個(gè)村民，但由于歷屆村長恐怖而且黑暗的魔法統(tǒng)治下泪电，村民們各自過著獨(dú)立的生活秆乳，完全沒有意識到其他n個(gè)人的存在懦鼠。
但有一天，村民xiba臻無意中也得到了魔法屹堰，并發(fā)現(xiàn)了這個(gè)恐怖的事實(shí)肛冶。為了反抗村長，他走遍了全世界扯键，找到了其他n個(gè)村民睦袖，并組織他們發(fā)動(dòng)革命。但讓這n個(gè)素不相識的村民（xiba臻已跟他們認(rèn)識）同心協(xié)力去抵抗村長是很困難的荣刑，所以xiba臻決定先讓他們互相認(rèn)識馅笙。
這里，xiba臻用了xiba村特有的xiba思維：先讓這n個(gè)人排成一列厉亏，并依次從1-n標(biāo)號延蟹。然后每次xiba臻會(huì)選出一個(gè)區(qū)間[l, r]，在這個(gè)區(qū)間中的人會(huì)去認(rèn)識其他在這個(gè)區(qū)間中的人叶堆，但已經(jīng)認(rèn)識過得不會(huì)再去認(rèn)識阱飘。這樣，進(jìn)行m次操作后虱颗，xiba臻認(rèn)為這n個(gè)人能認(rèn)識到許多人沥匈。
但是，為了精確地知道當(dāng)前有多少對人已經(jīng)認(rèn)識了忘渔，xiba臻想要知道每次操作后會(huì)新產(chǎn)生出多少對認(rèn)識的人高帖，但這已是xiba思維無法解決的事了，你能幫幫他嗎畦粮？
輸入：
第一行兩個(gè)整數(shù)n散址，m。
接下來m行每行兩個(gè)整數(shù)li宣赔，ri预麸，表示每次操作的區(qū)間。
輸出：
共m行儒将，每行一個(gè)整數(shù)ans_i吏祸，表示第i次操作后新產(chǎn)生出ans_i對認(rèn)識的人。
樣例輸入：
5 5
2 3
2 4
3 5
1 5
2 4
樣例輸出：
1
2
2
5
0
數(shù)據(jù)范圍限制：
對于20%的數(shù)據(jù)钩蚊，1≤n贡翘，m≤100蹈矮。
對于50%的數(shù)據(jù)，1≤n鸣驱，m≤5000泛鸟。
對于100%的數(shù)據(jù)，1≤n踊东，m≤300000北滥，1≤li≤ri≤n。
分析：
記f[i]為第i個(gè)人與f[i]—i-1的人認(rèn)識递胧，初始f[i]=i。
然后一次操作后f[i]=max{f[i],l} l<=i<=r ,同時(shí)統(tǒng)計(jì)答案赡茸。
O(nm)
實(shí)現(xiàn)：
#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;
int n,m,i,j,l,r;
long long ans,f[300001];
int main()
{
freopen("ohmygod.in","r",stdin);freopen("ohmygod.out","w",stdout);
scanf("%d%d",&n,&m);
for(i=1;i<=n;i++) f[i]=i;
while(m--)
{
scanf("%d%d",&l,&r);
ans=0;
for(i=r;i>=l;i--)
{
if(f[i]<=l) break;
if(l<f[i])
{
ans+=f[i]-l;
f[i]=l;
}
}
printf("%lld\n",ans);
}
}
