首页
题库
训练
讨论
比赛
作业
排名
real_hdsy_gyz
/ Vijos / 题库 / 棋盘上的士兵 /
题解
14 条题解
0
real_hdsy_gyz LV 0
发表您的题解
0

real_hdsy_gyz LV 0 @ 13 秒前

音饭标来书
燃视鞠较妖
塌而搭干茄
刻掩膛疏嚷
报歼耍痰侧
乐映叫奏垫
氏忙亡析绘
语鹰烦替诞
欣恢灾期补
肾石灯项泼
握及尾满宋
谈一胆变拣
膊拜裹向幅
巨脉棚作膝
土毒是歇纵
徒伶吴仿仁
州姻由拾著
纯异犯杜太
席罪姥乔克
库妈只胞呼
必订言逮狮
念培炼伟遥
针汉鞋县夜
礼疑泛懒胃
缠茂眼课圈
饼包空污谋
件竖律就蚁
愚字脖缎票
揭亿悉仙赛
垒棵佣戒宇
导翻购很轰
窜五街错岗
墓埋在困系
撇囊颈选仅
区伪点磨熟
愧林铁豪归
抖绝深注俘
愤贱父教筹
日蕉类诗贯
演诸婶携料
飞切数赌清
诉上宪络晓
叨云汁各惹
岁锦始脾底
震谜练虫府
毁蚀大瓦默
幕苹避增掉
极撤脂迹圾
槽消例精株
枕症衬馋耕
惨塑让慢王
话笔新炊蜓
蒙头养凝袖
戏乳娃论测
钟颤勺锡舰
峰神燕泉胳
退那厅鱼吗
捞遍网泄百
戚考梳滨威
辱咬裳雁末
馒正圣蓝奥
都匀蝇悟阀
状狐洒谁肿
虽记创哀司
闸迈算什事
悬隆捏啦滤
辞射沸答覆
样扶尸欠肯
恭借眨袭坚
披旱骗驱址
叹巾真逆模
牧的象嘉以
齿维充苗号
丹起学睁欲
门刷寄毯砌
启房差片豆
皇篮绳想夹
拿纳卷庭酸
锅究哨伞渴
馅条么吸藏
伐蛾棍惑盲
剖顿蛮辆戴
矿店史奖壶
军邪颗浓久
吩牺它秩泻
沙雷车应呆
魄税忽箭玉
堆价恒丈糟
臂匪旬慌嫂
闷添衣齐冒
朗滩船茎伙
辉输锹从良
盏萌助扒疯
菊尘谎鹅译
拼阳菌者提
蔑台含西巩
楼纺诵奴毕
疼尖洗占勉
您桑毛互涉
通乡芬体腿
猾伯校布现
对武辈桨先
触然凯杨辛
婆揪蓬隙肩
键裂哭暑暴
改轻财盒显
唯遭青难甜
市福档鸟催
康俱听棒逗
均双幻辫奇
额己朴魔誉
疤移惩曲查
春赠拍宙艳
鸣存搬稳刀
冰电连锤售
人酱怒治警
带摸议穿章
置唇随晶愉
弯婚分简故
烧肤求烟俊
鬼咳屈站吼
痕涨吉畅竹
鼻矮略热届
轿讽拘贷户
遗竟拴巡泳
矛播烤出安
惕筑酷萝概
完拔劫铜脊
桶疫凳格她
毫多乙饱础
富证搂公禽
息官悠推仗
案姿直柳铸
且纸习部梢
冶横舌穴估
倡亏稼节券
勾约帆虚职
禁释泰孕还
风所竿残虹
绵锋位静我
违蜂涂欺掏
候追德昆捡
趴叠玻省胖
苍僻骡识迁
酬胁母熊毅
计该写参殃
兆妻坊韵损
兵掌渗劳表
供啄社扬投
描瞧棋勿茫
删细术疗墨
着径举盐江
牛予紧陡景
跨鼠述走子
帘丽皆坛抬
最佳延厦盆
雅侵耗暗蝴
资里楚滋盈
倦历凶隐践
路哲霸漫实
框枝非乓跌
昏入熄印越
东响航倘疾
逼典秀铲机
单逢断辽遮
忘金搞众蹄
漏窃醒晌解
躲碗阔匆惭
遇即疲医傅
华季合迟娇
气行舟祝几
扩面定窄钱
扑副访纤超
灵悲球叔橘
槐盾障漆八
终属秒仆场
乌河璃具蛙
捧巴颂弹灶
页坐歉井此
螺杠善鹿锐
挎收附缴凉
厨扭蹈冻如
慕友密年留
榆睬化仔试
录把技老调
波软遵后严
疮葵笨千叼
薄刘读妨恰
茅滥党罚闲
淡胸罢恨撒
小弦形智领
棉摩法欧倒
醉于铅意压
沟壳洞膏预
加努死画亦
尤销永恩峡
稍狼嫌惯功
倍住尿猜冠
贴眠扇裕枪
光掀快贝万

0

lyyyzx LV 10 @ 5 年前
其实我是看了CQF的题解来做的,但我看不懂pascal代码:

链接: http://wenku.baidu.com/link?url=P-0X2nM7JOwI-9hoIlzi7syAC5OM3gb1wFDP-9J0f0yLj7MgOaUs5ObeqpSzuWPuGGWob4kDTJZf7EvmeHLsVQZht51-yFXrjRmjDdpYI3u

其实主要思路是斜向建立坐标系,每个士兵的控制范围就可以看作两个正方形的和(r>0),奇数一个,偶数一个,然后求矩形面积并线段数有一个(nlogn)的算法,最后是边界问题,还是有点麻烦，主要是数据预处理时注意一下就好了;

不懂的话自己画一下图,或者看CQF的题解,他写的非常详尽了。

##C++ code

#include <iostream>
#include <cstdio>
#include <algorithm>
using namespace std;
#define N 100010
typedef unsigned long long ull;

struct Line{
int x;
int y_up,y_down;
int cover;
};
bool operator <(Line a,Line b){
return a.x<b.x;
}
struct Tree{
int len;
int cover;
};
struct Range{
int l,r;
};
bool operator <(Range a,Range b){
return a.l<b.l;
}

int n,m,k;

Tree *tree;
int *y;
Line *line;
int *Len;
int *num;
int l,r,cover;//要更新的区间 值

Tree tree_odd[2*N*4];//线段树 odd表示奇数,eve表示偶数

Tree tree_eve[2*N*4];
int y_odd[2*N];//离散化纵坐标
int y_eve[2*N];
int len_odd;//离散化后的长度
int len_eve;
Line line_odd[2*N];//扫描线

Line line_eve[2*N];
int num_odd=-1;//扫描线的个数 从0开始存
int num_eve=-1;

Range tra[4][N];
int d[4]={-1,-1,-1,-1};
ull s[4];

inline void read(int& x){ //读入优化

char ch=getchar();
x=0;
while(ch>'9'||ch<'0'){
ch=getchar();
}
while('0'<=ch&&ch<='9'){
x=x*10+ch-'0';
ch=getchar();
}
}
inline void link(bool flag){//~链接
if(flag){
tree=tree_odd;
y=y_odd;
line=line_odd;
Len=&len_odd;
num=&num_odd;
}
else{
tree=tree_eve;
y=y_eve;
line=line_eve;
Len=&len_eve;
num=&num_eve;
}
}
int find(int x){
int l=0,r=*Len,mid=0;
while(l<r){
mid=(l+r)/2;
if(y[mid]==x)
return mid;
if(y[mid]<x) l=mid+1;
else r=mid;
}
return mid;
}
void init(){
int xx,yy,r;
int x1,x2,y1,y2,add;
read(n);read(m);read(k);
for(int i=0;i<k;i++){
read(xx);read(yy);read(r);
//从左上依次顺势针处理
int a[4]={yy+r-m-1,xx+r-n-1,-yy+r,-xx+r};//表示和边界相差的个数-1
int b[4]={1-xx,yy-m,xx-n,1-yy};
int c[4]={xx,yy,xx,yy};
for(int j=0;j<4;j++) {
if(a[j]<0) continue;
int up,down,nn;
down=c[j]-a[j];
up=c[j]+a[j];
tra[j][++d[j]].l=down;
tra[j][d[j]].r=up+2;
if((nn=a[j]+b[j])>0){
s[j]=max(s[j],(ull)nn*((ull)nn+1)/2);
}
}
for(int j=0;j<2;j++) {
link(add=(xx+yy+r)&1);
int &Num=*num;
x1=(xx+yy-r-add)/2;
y1=(yy-xx-r-add)/2;
x2=(xx+yy+r-add)/2+1;
y2=(yy-xx+r-add)/2+1;
y[++Num]=y1;
line[Num].x=x1;
line[Num].y_down=y1;
line[Num].y_up=y2;
line[Num].cover=1;
y[++Num]=y2;
line[Num].x=x2;
line[Num].y_down=y1;
line[Num].y_up=y2;
line[Num].cover=-1;
if(--r<0) break;
}
}
num_odd++;num_eve++;
sort(line_odd,line_odd+num_odd);
sort(line_eve,line_eve+num_eve);
sort(y_odd,y_odd+num_odd);
sort(y_eve,y_eve+num_eve);
len_odd=unique(y_odd,y_odd+num_odd)-y_odd;
len_eve=unique(y_eve,y_eve+num_eve)-y_eve;
for(int i=0;i<4;i++) sort(tra[i],tra[i]+(++d[i]));
}
inline void push(int root,int left,int right){
if(tree[root].cover>0)
tree[root].len=y[right+1]-y[left];
else if(left==right)
tree[root].len=0;
else
tree[root].len=tree[root<<1].len+tree[root<<1|1].len;
}
void update(int root,int left,int right){
if(r<left||right<l)
return;
if(l<=left&&right<=r){
tree[root].cover+=cover;
push(root,left,right);
return;
}
int mid=(left+right)/2;
update(root<<1,left,mid);
update(root<<1|1,mid+1,right);
push(root,left,right);
}
ull Pow(ull x){
return x*x;
}
ull ans1=0,ans2=0,ans;
int main(){
//freopen("in.txt","r",stdin);
init();//预处理
for(int j=0;j<2;j++){//计算矩形的并面积 无视边界
link(j);
for(int i=0;i<*num-1;i++){
l=find(line[i].y_down);
r=find(line[i].y_up)-1;
cover=line[i].cover;
update(1,0,*Len-1);
ans1+=(ull)tree[1].len*(ull)(line[i+1].x-line[i].x);
}
}
Range t;
for(int i=0;i<4;i++){//计算棋盘外重叠三角形的面积 分四个面最后还要减去重叠的部分
t.l=tra[i][0].l;
t.r=tra[i][0].r;
ans2+=Pow((ull)(t.r-t.l)/2);
for(int j=1;j<d[i];j++){
if(t.r>=tra[i][j].r) //包含
continue;
else if(t.r<=tra[i][j].l){ //无交集

ans2+=Pow((ull)(tra[i][j].r-tra[i][j].l)/2);
t.r=tra[i][j].r;
t.l=tra[i][j].l;
}
else {//相交 自己画一下图推一下公式

ull add,nn;
ans2+=Pow((tra[i][j].r-tra[i][j].l)/2);
nn=t.r-tra[i][j].l;
if(nn&1) add=Pow((nn-1)/2)+(nn-1)/2;//这里公式推错,WA n次
else add=Pow(nn/2);
ans2-=add;
t.r=tra[i][j].r;
t.l=tra[i][j].l;
}
}
}
ans=ans1-(ans2-s[0]-s[1]-s[2]-s[3]);
cout<<ans<<endl;
return 0;
}

0

ckl8520 LV 10 @ 12 年前
Orz Lazio神牛。。

C++程序只有110+行。。

小菜的有270+= =|

太悲剧了。。

0

怪盗~基德 LV 10 @ 12 年前
我很无语,我也很抑郁,为什么CQF神牛的程序只有200多行,我的有356行,跑得还比我快......我写的是很标准的线段树,而CQF神牛就只用了一对链表就搞定了,绝对要膜拜ORZ!!!!!!!!!!!!!!!!!!!!

0

ipip2005 LV 10 @ 12 年前
只会一个不敢写的：把矩形四条边各加一个三角形（边长为偶数时是接近三角形），以每条斜线段作为大线段树上的元素，再根据各条斜线段上的点集内套一颗小线段树，最后维护出所占面积，因为每次斜线段上分配的点数不同，且相邻两条斜线段是不同的。就把所有斜线段从左到右以1~m+n-1编号，奇编号进线段树1，偶编号进线段树2，要维护两棵二维线段树，还要离散化!!!

恶心！O(k(logk)^2)

PS：好像不是预期的很优很简单，而是很烦很暴力，题解何处觅？

LS发你的空间地址干什么，没有题解啊

哈哈哦，OIBH上有题解，太大了，有很多图，就不发这里了

貌似题解里的也是双二维线段树，不知为何klogk 而不是klogklogk 了

哦，原来是经典例题火星地图的做法~~

0

董 LV 10 @ 12 年前
http://hi.baidu.com/%CB%D5%CC%DAsauterne

0

oimaster LV 10 @ 12 年前
看了cqf的标称，先Orz……

注意在负数的时候不能用shr 1实现div 2

0

pzy3303 LV 10 @ 13 年前
历时3天，终于AC牛题了

0

lsz@ts LV 3 @ 14 年前
经典的Shaping Regions...

0

epicwu LV 4 @ 14 年前
奶奶的，自己编的怎么都要超2个点，90分

只好把cqf的标程交了

0

qq311755010 LV 3 @ 14 年前
cheat?cheat!

0

luziying LV 6 @ 15 年前
只知道一个算法，相当烦

0

BYSnowpine LV 4 @ 15 年前
用线段树logn的维护复杂度

nlogn的总时间能不能过?

0

YJ狗狗 LV 6 @ 15 年前
CQF的题..又来了..

1
棋盘上的士兵
查看题目
递交
讨论
题解
信息
ID1231递交 Accepted难度6分类点击显示标签
CQF
递交数130我的递交数1已通过35通过率27%被复制2上传者 cqf
状态
评测队列
服务状态
开发
开源
API
支持
帮助
QQ 群
关于联系我们隐私服务条款版权申诉 Language
© 2005 - 2021 Vijos.orgbuild20210206-1-gb0e1685沪ICP备14040537号-1

音饭标来书
燃视鞠较妖
塌而搭干茄
刻掩膛疏嚷
报歼耍痰侧
乐映叫奏垫
氏忙亡析绘
语鹰烦替诞
欣恢灾期补
肾石灯项泼
握及尾满宋
谈一胆变拣
膊拜裹向幅
巨脉棚作膝
土毒是歇纵
徒伶吴仿仁
州姻由拾著
纯异犯杜太
席罪姥乔克
库妈只胞呼
必订言逮狮
念培炼伟遥
针汉鞋县夜
礼疑泛懒胃
缠茂眼课圈
饼包空污谋
件竖律就蚁
愚字脖缎票
揭亿悉仙赛
垒棵佣戒宇
导翻购很轰
窜五街错岗
墓埋在困系
撇囊颈选仅
区伪点磨熟
愧林铁豪归
抖绝深注俘
愤贱父教筹
日蕉类诗贯
演诸婶携料
飞切数赌清
诉上宪络晓
叨云汁各惹
岁锦始脾底
震谜练虫府
毁蚀大瓦默
幕苹避增掉
极撤脂迹圾
槽消例精株
枕症衬馋耕
惨塑让慢王
话笔新炊蜓
蒙头养凝袖
戏乳娃论测
钟颤勺锡舰
峰神燕泉胳
退那厅鱼吗
捞遍网泄百
戚考梳滨威
辱咬裳雁末
馒正圣蓝奥
都匀蝇悟阀
状狐洒谁肿
虽记创哀司
闸迈算什事
悬隆捏啦滤
辞射沸答覆
样扶尸欠肯
恭借眨袭坚
披旱骗驱址
叹巾真逆模
牧的象嘉以
齿维充苗号
丹起学睁欲
门刷寄毯砌
启房差片豆
皇篮绳想夹
拿纳卷庭酸
锅究哨伞渴
馅条么吸藏
伐蛾棍惑盲
剖顿蛮辆戴
矿店史奖壶
军邪颗浓久
吩牺它秩泻
沙雷车应呆
魄税忽箭玉
堆价恒丈糟
臂匪旬慌嫂
闷添衣齐冒
朗滩船茎伙
辉输锹从良
盏萌助扒疯
菊尘谎鹅译
拼阳菌者提
蔑台含西巩
楼纺诵奴毕
疼尖洗占勉
您桑毛互涉
通乡芬体腿
猾伯校布现
对武辈桨先
触然凯杨辛
婆揪蓬隙肩
键裂哭暑暴
改轻财盒显
唯遭青难甜
市福档鸟催
康俱听棒逗
均双幻辫奇
额己朴魔誉
疤移惩曲查
春赠拍宙艳
鸣存搬稳刀
冰电连锤售
人酱怒治警
带摸议穿章
置唇随晶愉
弯婚分简故
烧肤求烟俊
鬼咳屈站吼
痕涨吉畅竹
鼻矮略热届
轿讽拘贷户
遗竟拴巡泳
矛播烤出安
惕筑酷萝概
完拔劫铜脊
桶疫凳格她
毫多乙饱础
富证搂公禽
息官悠推仗
案姿直柳铸
且纸习部梢
冶横舌穴估
倡亏稼节券
勾约帆虚职
禁释泰孕还
风所竿残虹
绵锋位静我
违蜂涂欺掏
候追德昆捡
趴叠玻省胖
苍僻骡识迁
酬胁母熊毅
计该写参殃
兆妻坊韵损
兵掌渗劳表
供啄社扬投
描瞧棋勿茫
删细术疗墨
着径举盐江
牛予紧陡景
跨鼠述走子
帘丽皆坛抬
最佳延厦盆
雅侵耗暗蝴
资里楚滋盈
倦历凶隐践
路哲霸漫实
框枝非乓跌
昏入熄印越
东响航倘疾
逼典秀铲机
单逢断辽遮
忘金搞众蹄
漏窃醒晌解
躲碗阔匆惭
遇即疲医傅
华季合迟娇
气行舟祝几
扩面定窄钱
扑副访纤超
灵悲球叔橘
槐盾障漆八
终属秒仆场
乌河璃具蛙
捧巴颂弹灶
页坐歉井此
螺杠善鹿锐
挎收附缴凉
厨扭蹈冻如
慕友密年留
榆睬化仔试
录把技老调
波软遵后严
疮葵笨千叼
薄刘读妨恰
茅滥党罚闲
淡胸罢恨撒
小弦形智领
棉摩法欧倒
醉于铅意压
沟壳洞膏预
加努死画亦
尤销永恩峡
稍狼嫌惯功
倍住尿猜冠
贴眠扇裕枪
光掀快贝万

其实我是看了CQF的题解来做的,但我看不懂pascal代码:

链接: http://wenku.baidu.com/link?url=P-0X2nM7JOwI-9hoIlzi7syAC5OM3gb1wFDP-9J0f0yLj7MgOaUs5ObeqpSzuWPuGGWob4kDTJZf7EvmeHLsVQZht51-yFXrjRmjDdpYI3u

其实主要思路是斜向建立坐标系,每个士兵的控制范围就可以看作两个正方形的和(r>0),奇数一个,偶数一个,然后求矩形面积并线段数有一个(nlogn)的算法,最后是边界问题,还是有点麻烦，主要是数据预处理时注意一下就好了;

不懂的话自己画一下图,或者看CQF的题解,他写的非常详尽了。

##C++ code

#include <iostream>
#include <cstdio>
#include <algorithm>
using namespace std;
#define N 100010
typedef unsigned long long ull;

struct Line{
int x;
int y_up,y_down;
int cover;
};
bool operator <(Line a,Line b){
return a.x<b.x;
}
struct Tree{
int len;
int cover;
};
struct Range{
int l,r;
};
bool operator <(Range a,Range b){
return a.l<b.l;
}

int n,m,k;

Tree *tree;
int *y;
Line *line;
int *Len;
int *num;
int l,r,cover;//要更新的区间 值

Tree tree_odd[2*N*4];//线段树 odd表示奇数,eve表示偶数

Tree tree_eve[2*N*4];
int y_odd[2*N];//离散化纵坐标
int y_eve[2*N];
int len_odd;//离散化后的长度
int len_eve;
Line line_odd[2*N];//扫描线

Line line_eve[2*N];
int num_odd=-1;//扫描线的个数 从0开始存
int num_eve=-1;

Range tra[4][N];
int d[4]={-1,-1,-1,-1};
ull s[4];

inline void read(int& x){ //读入优化

char ch=getchar();
x=0;
while(ch>'9'||ch<'0'){
ch=getchar();
}
while('0'<=ch&&ch<='9'){
x=x*10+ch-'0';
ch=getchar();
}
}
inline void link(bool flag){//~链接
if(flag){
tree=tree_odd;
y=y_odd;
line=line_odd;
Len=&len_odd;
num=&num_odd;
}
else{
tree=tree_eve;
y=y_eve;
line=line_eve;
Len=&len_eve;
num=&num_eve;
}
}
int find(int x){
int l=0,r=*Len,mid=0;
while(l<r){
mid=(l+r)/2;
if(y[mid]==x)
return mid;
if(y[mid]<x) l=mid+1;
else r=mid;
}
return mid;
}
void init(){
int xx,yy,r;
int x1,x2,y1,y2,add;
read(n);read(m);read(k);
for(int i=0;i<k;i++){
read(xx);read(yy);read(r);
//从左上依次顺势针处理
int a[4]={yy+r-m-1,xx+r-n-1,-yy+r,-xx+r};//表示和边界相差的个数-1
int b[4]={1-xx,yy-m,xx-n,1-yy};
int c[4]={xx,yy,xx,yy};
for(int j=0;j<4;j++) {
if(a[j]<0) continue;
int up,down,nn;
down=c[j]-a[j];
up=c[j]+a[j];
tra[j][++d[j]].l=down;
tra[j][d[j]].r=up+2;
if((nn=a[j]+b[j])>0){
s[j]=max(s[j],(ull)nn*((ull)nn+1)/2);
}
}
for(int j=0;j<2;j++) {
link(add=(xx+yy+r)&1);
int &Num=*num;
x1=(xx+yy-r-add)/2;
y1=(yy-xx-r-add)/2;
x2=(xx+yy+r-add)/2+1;
y2=(yy-xx+r-add)/2+1;
y[++Num]=y1;
line[Num].x=x1;
line[Num].y_down=y1;
line[Num].y_up=y2;
line[Num].cover=1;
y[++Num]=y2;
line[Num].x=x2;
line[Num].y_down=y1;
line[Num].y_up=y2;
line[Num].cover=-1;
if(--r<0) break;
}
}
num_odd++;num_eve++;
sort(line_odd,line_odd+num_odd);
sort(line_eve,line_eve+num_eve);
sort(y_odd,y_odd+num_odd);
sort(y_eve,y_eve+num_eve);
len_odd=unique(y_odd,y_odd+num_odd)-y_odd;
len_eve=unique(y_eve,y_eve+num_eve)-y_eve;
for(int i=0;i<4;i++) sort(tra[i],tra[i]+(++d[i]));
}
inline void push(int root,int left,int right){
if(tree[root].cover>0)
tree[root].len=y[right+1]-y[left];
else if(left==right)
tree[root].len=0;
else
tree[root].len=tree[root<<1].len+tree[root<<1|1].len;
}
void update(int root,int left,int right){
if(r<left||right<l)
return;
if(l<=left&&right<=r){
tree[root].cover+=cover;
push(root,left,right);
return;
}
int mid=(left+right)/2;
update(root<<1,left,mid);
update(root<<1|1,mid+1,right);
push(root,left,right);
}
ull Pow(ull x){
return x*x;
}
ull ans1=0,ans2=0,ans;
int main(){
//freopen("in.txt","r",stdin);
init();//预处理
for(int j=0;j<2;j++){//计算矩形的并面积 无视边界
link(j);
for(int i=0;i<*num-1;i++){
l=find(line[i].y_down);
r=find(line[i].y_up)-1;
cover=line[i].cover;
update(1,0,*Len-1);
ans1+=(ull)tree[1].len*(ull)(line[i+1].x-line[i].x);
}
}
Range t;
for(int i=0;i<4;i++){//计算棋盘外重叠三角形的面积 分四个面最后还要减去重叠的部分
t.l=tra[i][0].l;
t.r=tra[i][0].r;
ans2+=Pow((ull)(t.r-t.l)/2);
for(int j=1;j<d[i];j++){
if(t.r>=tra[i][j].r) //包含
continue;
else if(t.r<=tra[i][j].l){ //无交集

ans2+=Pow((ull)(tra[i][j].r-tra[i][j].l)/2);
t.r=tra[i][j].r;
t.l=tra[i][j].l;
}
else {//相交 自己画一下图推一下公式

ull add,nn;
ans2+=Pow((tra[i][j].r-tra[i][j].l)/2);
nn=t.r-tra[i][j].l;
if(nn&1) add=Pow((nn-1)/2)+(nn-1)/2;//这里公式推错,WA n次
else add=Pow(nn/2);
ans2-=add;
t.r=tra[i][j].r;
t.l=tra[i][j].l;
}
}
}
ans=ans1-(ans2-s[0]-s[1]-s[2]-s[3]);
cout<<ans<<endl;
return 0;
}

Orz Lazio神牛。。

C++程序只有110+行。。

小菜的有270+= =|

太悲剧了。。

我很无语,我也很抑郁,为什么CQF神牛的程序只有200多行,我的有356行,跑得还比我快......我写的是很标准的线段树,而CQF神牛就只用了一对链表就搞定了,绝对要膜拜ORZ!!!!!!!!!!!!!!!!!!!!

只会一个不敢写的：把矩形四条边各加一个三角形（边长为偶数时是接近三角形），以每条斜线段作为大线段树上的元素，再根据各条斜线段上的点集内套一颗小线段树，最后维护出所占面积，因为每次斜线段上分配的点数不同，且相邻两条斜线段是不同的。就把所有斜线段从左到右以1~m+n-1编号，奇编号进线段树1，偶编号进线段树2，要维护两棵二维线段树，还要离散化!!!

恶心！O(k(logk)^2)

PS：好像不是预期的很优很简单，而是很烦很暴力，题解何处觅？

LS发你的空间地址干什么，没有题解啊

哈哈哦，OIBH上有题解，太大了，有很多图，就不发这里了

貌似题解里的也是双二维线段树，不知为何klogk 而不是klogklogk 了

哦，原来是经典例题火星地图的做法~~

http://hi.baidu.com/%CB%D5%CC%DAsauterne

看了cqf的标称，先Orz……

注意在负数的时候不能用shr 1实现div 2

历时3天，终于AC牛题了

经典的Shaping Regions...

奶奶的，自己编的怎么都要超2个点，90分

只好把cqf的标程交了

cheat?cheat!

只知道一个算法，相当烦

用线段树logn的维护复杂度

nlogn的总时间能不能过?

CQF的题..又来了..