编译通过...

├ 测试数据 01：答案正确... 0ms

├ 测试数据 02：答案正确... 0ms

├ 测试数据 03：答案正确... 0ms

├ 测试数据 04：答案正确... 0ms

├ 测试数据 05：答案正确... 134ms

├ 测试数据 06：答案正确... 150ms

├ 测试数据 07：答案正确... 259ms

├ 测试数据 08：答案正确... 150ms

├ 测试数据 09：答案正确... 275ms

├ 测试数据 10：答案正确... 134ms

---|---|---|---|---|---|---|---|-

Accepted 有效得分：100 有效耗时：1102ms

话说耗时都不是很理想。。

一开始想法就对了，竟然交了6次（其中n次开小数组，唉，做人不能太抠门），还碰到vj被卡，rp啊

顺便orzLX...神牛

用一种稍有别于括号的想法得到了相同的算法，我的题解

编译通过...

├ 测试数据 01：答案正确... 0ms

├ 测试数据 02：答案正确... 0ms

├ 测试数据 03：答案正确... 0ms

├ 测试数据 04：答案正确... 0ms

├ 测试数据 05：答案正确... 119ms

├ 测试数据 06：答案正确... 400ms

├ 测试数据 07：答案正确... 181ms

├ 测试数据 08：答案正确... 541ms

├ 测试数据 09：答案正确... 634ms

├ 测试数据 10：答案正确... 369ms

---|---|---|---|---|---|---|---|-

Accepted 有效得分：100 有效耗时：2244ms

呃~果然我是最笨的~~方法就是跟1663一样，加了一个树状数组…………

^我人品都花在这了^70分都AC^

erer

看别人得题解看得头晕发恶心才终于看懂。。。。。。说真的，真的是看之前好好的，看完头晕发恶心。

Flag 　　

题号 　　P1664

类型(?) 　　其它

通过 　　22人

提交 　　66次

通过率 　　33%

难度 　　0

http://user.qzone.qq.com/281589210/blog/1255232846

我的题解

下面教主的题解不是一般人能够看懂的（包括我）

编译通过...

├ 测试数据 01：答案正确... 0ms

├ 测试数据 02：答案正确... 0ms

├ 测试数据 03：答案正确... 0ms

├ 测试数据 04：答案正确... 0ms

├ 测试数据 05：答案正确... 103ms

├ 测试数据 06：答案正确... 166ms

├ 测试数据 07：答案正确... 181ms

├ 测试数据 08：答案正确... 353ms

├ 测试数据 09：答案正确... 353ms

├ 测试数据 10：答案正确... 228ms

---|---|---|---|---|---|---|---|-

Accepted 有效得分：100 有效耗时：1384ms

var

map , right , sum : array [ 0 .. 1000 , 1 .. 1000 ] of longint;

now : array [ 1 .. 1000000 , 1 .. 2 ] of longint;

vis : array [ 1 .. 1000 , 1 .. 1000 ] of boolean;

tot : array [ 1 .. 1001 ] of longint;

n , m , ans : longint;

procedure main;

var

i , j , k , s , t : longint;

begin

for j := 1 to m do

begin

for i := 1 to n do

begin

k := map[i , j];

if vis[i , j] then

if now[k , 1] = 0 then

begin

inc(tot[i]); dec(tot[right[i , j]]);

now[k , 1] := i; now[k , 2] := right[i , j];

end

else begin

s := now[k , 1]; t := now[k , 2];

dec(tot); inc(tot[t]);

if (i >= s) and (i < t) then t := i;

if i < s then begin t := s; s := i; end;

if t > right[i , j] then t := right[i , j];

inc(tot); dec(tot[t]);

now[k , 1] := s; now[k , 2] := t;

end;

sum[i , j] := sum[i-1 , j] + tot[i];

end;

end;

for i := 1 to n do

begin

for j := 1 to m do

ans := ans xor sum[i , j];

end;

writeln(ans);

end;

procedure init;

var

i , j , k : longint;

begin

readln(n , m);

for i := 1 to n do

for j := 1 to m do read(map[i , j]);

for j := 1 to m do

for i := 1 to n do

begin

k := map[i , j];

if (now[k , 2] < j) then

begin

now[k , 1] := i; now[k , 2] := j;

vis[i , j] := true;

right[i , j] := n+1;

continue;

end;

if right[now[k , 1] , j] = n+1 then

begin

right[now[k , 1] , now[k , 2]] := i;

end;

end;

fillchar(now , sizeof(now) , 0);

end;

begin

init;

main;

end.

想了许久,才想了一个好写点的!

编译通过...

├ 测试数据 01：答案正确... 0ms

├ 测试数据 02：答案正确... 0ms

├ 测试数据 03：答案正确... 0ms

├ 测试数据 04：答案正确... 0ms

├ 测试数据 05：答案正确... 353ms

├ 测试数据 06：答案正确... 556ms

├ 测试数据 07：答案正确... 556ms

├ 测试数据 08：答案正确... 931ms

├ 测试数据 09：答案正确... 962ms

├ 测试数据 10：答案正确... 853ms

---|---|---|---|---|---|---|---|-

Accepted 有效得分：100 有效耗时：4211ms

sunny好慢啊

编译通过...

├ 测试数据 01：答案正确... 0ms

├ 测试数据 02：答案正确... 0ms

├ 测试数据 03：答案正确... 0ms

├ 测试数据 04：答案正确... 0ms

├ 测试数据 05：答案正确... 25ms

├ 测试数据 06：答案正确... 119ms

├ 测试数据 07：答案正确... 88ms

├ 测试数据 08：答案正确... 259ms

├ 测试数据 09：答案正确... 181ms

├ 测试数据 10：答案正确... 197ms

---|---|---|---|---|---|---|---|-

Accepted 有效得分：100 有效耗时：869ms

啊...沙茶了~~

真的没必要用数据结构，这题改完也挺水的...

http://user.qzone.qq.com/740436286/infocenter?ptlang=2052

这题还想过要用线段树，以后真该认真分析题目

想得再透彻些，orz做出的牛人们！！！

枚举数字，然后通过扫描线把问题转化成：

有N*M个格子，N行M列，初始值为0，每次，将坐标为(x1,y1)à(x2,y2)这个矩形内的格子的值全部+c，求出所有格子的最后的值。

该问题可以这么解决：

f[i][j]=f[j]-上边穿越(i+1,j)的矩形的值和(令其为c(i+1,j))+下边穿越(i,j)的矩形的值的和(令其为d(i,j))。

如何求c(i,j)呢？其实c(i,j)=c(i,j-1)-右上角在(i,j-1)的矩形的值的和+左上角在(i,j)的矩形的值的和。

d(i,j)同理。

至此，该问题解决。

................

AC了，速度巨慢（用了getchar读入）：

├ 测试数据 01：答案正确... 0ms

├ 测试数据 02：答案正确... 0ms

├ 测试数据 03：答案正确... 0ms

├ 测试数据 04：答案正确... 0ms

├ 测试数据 05：答案正确... 56ms

├ 测试数据 06：答案正确... 228ms

├ 测试数据 07：答案正确... 197ms

├ 测试数据 08：答案正确... 416ms

├ 测试数据 09：答案正确... 400ms

├ 测试数据 10：答案正确... 338ms

---|---|---|---|---|---|---|---|-

Accepted 有效得分：100 有效耗时：1635ms

强烈膜拜fjxmlhx神牛！！！！！！！！！！！！！！！！！

有没有人告诉我怎么做啊

c++中scanf和getchar好像都挺快的

pascal应该好过很多

占