CF 100735 F 解题报告
393行,也是够了
题意:感谢@似水流年 的翻译
链接:http://codeforces.com/gym/100735/problem/F
给你一堆椭圆,你要进行这些处理
1,将[l,r]的ai修改为v
2,将[l,r]的bi修改为v
3,将[l,r]的ai加上v
4,将[l,r]的bi加上v
5,求编号[l,r]之间椭圆面积之和/pi(根据椭圆面积公式,S=ai*bi*pi,所以直接是计算ai*bi的和)
6,求[l,r]内有多少个椭圆
***规则:一个椭圆,如果ai<=0或bi<=0那么就会消失,再也不会出现.一个椭圆,如果ai>A或者bi>B,那么它就会被扔进垃圾桶,再也不会出现
下面
是absi2011的算法:
是absi2011的算法:
分1000块维护这些椭圆,每块100个(为啥不分sqrt(n),理由马上告诉你)
那么每次修改就维护个tag
如果是部分修改就大暴力然后该删删
如果整体修改,有消失的也当部分修改做
因为每个只会消失一次,所以最多消失的复杂度是O(100n),没关系
每次暴力一遍,不考虑消失这种情况,是O(1000)的,似乎也没太大关系,毕竟整体修改常数小..
注意几个问题:
1,标记维护,容易出错
2,对于1或者2操作v非法应该全部处死的时候,不要吝啬时间= =不然会带来很多麻烦
代码:
#include<set>
#include<map>
#include<list>
#include<queue>
#include<stack>
#include<math.h>
#include<string>
#include<time.h>
#include<bitset>
#include<vector>
#include<memory>
#include<utility>
#include<stdio.h>
#include<sstream>
#include<fstream>
#include<iostream>
#include<stdlib.h>
#include<string.h>
#include<algorithm>
using namespace std;
int a[100005];
int b[100005];
const int block_max=1005;
long long sum[block_max];
int suma[block_max];
int sumb[block_max];
int alive[block_max];
int maxa[block_max];
int mina[block_max];
int maxb[block_max];
int minb[block_max];
int taga[block_max];
int tagb[block_max];
int tag_kind_a[block_max];
int tag_kind_b[block_max];
int oper[100005];
int oper_num[100005][3];
int max_a,max_b;
const int block_size=200;
int n;
int block_n;
long long ans=0;
void update(int num)
{
int i;
int l=num*block_size;
int r=(num+1)*block_size;
sum[num]=0;
suma[num]=0;
sumb[num]=0;
maxa[num]=0;
maxb[num]=0;
mina[num]=max_a;
minb[num]=max_b;
tag_kind_a[num]=0;
tag_kind_b[num]=0;
for (i=l;i<r;i++)
{
if (a[i]==-999999999) continue;
if ((a[i]<=0)||(b[i]<=0)||(a[i]>max_a)||(b[i]>max_b))
{
a[i]=-999999999;
alive[num]--;
continue;
}
suma[num]+=a[i];
sumb[num]+=b[i];
maxa[num]=max(maxa[num],a[i]);
maxb[num]=max(maxb[num],b[i]);
mina[num]=min(mina[num],a[i]);
minb[num]=min(minb[num],b[i]);
sum[num]+=(long long)a[i]*b[i];
}
}
void break_tag_a(int num)
{
if (tag_kind_a[num]==0)
{
return;
}
int l=num*block_size;
int r=(num+1)*block_size;
int i;
for (i=l;i<r;i++)
{
if (a[i]<=0) continue;
if (tag_kind_a[num]==1)
{
a[i]=taga[num];
}
else if (tag_kind_a[num]==2)
{
a[i]+=taga[num];
}
}
tag_kind_a[num]=0;
}
void break_tag_b(int num)
{
if (tag_kind_b[num]==0)
{
return;
}
int l=num*block_size;
int r=(num+1)*block_size;
int i;
for (i=l;i<r;i++)
{
if (a[i]<=0) continue;
if (tag_kind_b[num]==1)
{
b[i]=tagb[num];
}
else if (tag_kind_b[num]==2)
{
b[i]+=tagb[num];
}
}
tag_kind_b[num]=0;
}
void change1_part(int l,int r,int val)
{
int num=l/block_size;
break_tag_a(num);
break_tag_b(num);
int i;
for (i=l;i<r;i++)
{
if (a[i]<=0) continue;
a[i]=val;
}
update(num);
}
void change2_part(int l,int r,int val)
{
int num=l/block_size;
break_tag_a(num);
break_tag_b(num);
int i;
for (i=l;i<r;i++)
{
if (a[i]<=0) continue;
b[i]=val;
}
update(num);
}
void change3_part(int l,int r,int val)
{
int num=l/block_size;
break_tag_a(num);
break_tag_b(num);
int i;
for (i=l;i<r;i++)
{
if (a[i]<=0) continue;
a[i]+=val;
}
update(num);
}
void change4_part(int l,int r,int val)
{
int num=l/block_size;
break_tag_a(num);
break_tag_b(num);
int i;
for (i=l;i<r;i++)
{
if (a[i]<=0) continue;
b[i]+=val;
}
update(num);
}
void query1_part(int l,int r)
{
int num=l/block_size;
break_tag_a(num);
break_tag_b(num);
int i;
for (i=l;i<r;i++)
{
if (a[i]<=0) continue;
ans+=(long long)a[i]*b[i];
}
}
void query2_part(int l,int r)
{
int num=l/block_size;
break_tag_a(num);
break_tag_b(num);
int i;
for (i=l;i<r;i++)
{
if (a[i]<=0) continue;
ans++;
}
}
void change1_full(int num,int val)
{
if (alive[num]==0) return;
if ((val>max_a)||(val<=0))
{
change1_part(num*block_size,(num+1)*block_size,val);
return;
}
suma[num]=alive[num]*val;
sum[num]=sumb[num]*(long long)val;
maxa[num]=val;
mina[num]=val;
taga[num]=val;
tag_kind_a[num]=1;
}
void change2_full(int num,int val)
{
if (alive[num]==0) return;
if ((val>max_b)||(val<=0))
{
change2_part(num*block_size,(num+1)*block_size,val);
return;
}
sumb[num]=alive[num]*val;
sum[num]=suma[num]*(long long)val;
maxb[num]=val;
minb[num]=val;
tagb[num]=val;
tag_kind_b[num]=1;
}
void change3_full(int num,int val)
{
if (alive[num]==0) return;
if ((maxa[num]+val>max_a)||(mina[num]+val<=0))
{
change3_part(num*block_size,(num+1)*block_size,val);
return;
}
suma[num]+=alive[num]*val;
sum[num]+=sumb[num]*(long long)val;
maxa[num]+=val;
mina[num]+=val;
if (tag_kind_a[num]==0)
{
taga[num]=val;
tag_kind_a[num]=2;
}
else
{
taga[num]+=val;
}
}
void change4_full(int num,int val)
{
if (alive[num]==0) return;
if ((maxb[num]+val>max_b)||(minb[num]+val<=0))
{
change4_part(num*block_size,(num+1)*block_size,val);
return;
}
sumb[num]+=alive[num]*val;
sum[num]+=suma[num]*(long long)val;
maxb[num]+=val;
minb[num]+=val;
if (tag_kind_b[num]==0)
{
tagb[num]=val;
tag_kind_b[num]=2;
}
else
{
tagb[num]+=val;
}
}
void query1_full(int num)
{
ans+=sum[num];
}
void query2_full(int num)
{
ans+=alive[num];
}
void full_change(int num,int oper,int val)
{
if (oper==1)
{
change1_full(num,val);
}
if (oper==2)
{
change2_full(num,val);
}
if (oper==3)
{
change3_full(num,val);
}
if (oper==4)
{
change4_full(num,val);
}
if (oper==5)
{
query1_full(num);
}
if (oper==6)
{
query2_full(num);
}
}
void part_change(int num,int l,int r,int oper,int val)
{
if (oper==1)
{
change1_part(l,r,val);
}
if (oper==2)
{
change2_part(l,r,val);
}
if (oper==3)
{
change3_part(l,r,val);
}
if (oper==4)
{
change4_part(l,r,val);
}
if (oper==5)
{
query1_part(l,r);
}
if (oper==6)
{
query2_part(l,r);
}
}
void spilt(int l,int r,int oper,int val)
{
int i;
for (i=0;i<block_n;i++)
{
int start=i*block_size;
int end=(i+1)*block_size;
if ((start>=r)||(end<=l)) continue;
if ((l<=start)&&(end<=r))
{
full_change(i,oper,val);
}
else
{
part_change(i,max(start,l),min(end,r),oper,val);
}
}
if (oper>4)
{
cout<<ans<<'\n';
}
}
int main()
{
#ifdef absi2011
freopen("input.txt","r",stdin);
freopen("output.txt","w",stdout);
#endif
int m;
scanf("%d%d",&n,&m);
block_n=(n-1)/block_size+1;
int i;
for (i=0;i<n;i++)
{
scanf("%d%d",&a[i],&b[i]);
}
for (i=0;i<m;i++)
{
scanf("%d",&oper[i]);
scanf("%d",&oper_num[i][0]);
oper_num[i][0]--;
scanf("%d",&oper_num[i][1]);
if (oper[i]<=4)
{
scanf("%d",&oper_num[i][2]);
}
}
scanf("%d%d",&max_a,&max_b);
for (i=0;i<block_n;i++)
{
alive[i]=block_size;
update(i);
}
ios::sync_with_stdio(false);
for (i=0;i<m;i++)
{
ans=0;
spilt(oper_num[i][0],oper_num[i][1],oper[i],oper_num[i][2]);
}
return 0;
}
评论 (0)