#include <iostream>
#include <cstdio>
#include <cstring>
#include <algorithm>
#include <cmath>
using namespace std;
#define FOR(i,n) for (int i=1;i<=n;i++)

const int maxn=1000+10;
int n,m;
int a[maxn][maxn];
int b[maxn][maxn][4];
int f[maxn][maxn];
int d[maxn][maxn];
int g[maxn][maxn][4];
struct info {
    int v,pos;
};
info t[maxn];
int cnt[maxn][maxn];
int tot;
int ans;
void mc(int x,int y,int x2,int y2) {
    if (x==x2) {
        if (y>y2) swap(y,y2);
        for (int i=y;i<=y2;i++) {
            a[x][i]=1;
            if (i!=y) {
                g[x][i][0]=1;
                g[x][i-1][2]=1;
            }
        }
    } else if (y==y2) {
        if (x>x2) swap(x,x2);
        for (int i=x;i<=x2;i++) {
            a[i][y]=1;
            if (i!=x) {
                g[i][y][1]=1;
                g[i-1][y][3]=1;
            }
        }
    }
}
bool cmp(info x,info y) {
    return x.v<y.v;
}
int c[3*maxn];
int lowbit(int x) {
    return x&-x;
}
void add(int x,int v) {
    while (x<=n) {
        c[x]+=v;
        x+=lowbit(x);
    }
}
int sum(int x) {
    int res=0;
    while (x>=1) {
        res+=c[x];
        x-=lowbit(x);
    }
    return res;
}
int query(int x,int y) {
    return sum(y)-sum(x-1);
}
int ok(int x,int y) {
    return x>=1&&x<=n&&y>=1&&y<=n;
}
int main() {
    scanf("%d%d",&n,&m);
    FOR(i,m) {
        int x=0,y=0,x2=0,y2=0;
        scanf("%d%d%d%d",&x,&y,&x2,&y2);
        mc(x+1,y+1,x2+1,y2+1);
    }
    n++;
    FOR(i,n) FOR(j,n) {
        if (a[i][j]) {
            b[i][j][0]=0;
            if (!ok(i,j-1)) continue;
            if (g[i][j][0]) b[i][j][0]=b[i][j-1][0]+1;
        }
    }
    FOR(i,n) FOR(j,n) {
        if (a[i][j]) {
            b[i][j][1]=0;
            if (!ok(i-1,j)) continue;
            if (g[i][j][1]) b[i][j][1]=b[i-1][j][1]+1;
        }
    }
    for (int i=n;i>=1;i--) for (int j=n;j>=1;j--) {
        if (a[i][j]) {
            b[i][j][2]=0;
            if (!ok(i,j+1)) continue;
            if (g[i][j][2]) b[i][j][2]=b[i][j+1][2]+1;
        }
    }
    for (int i=n;i>=1;i--) for (int j=n;j>=1;j--) {
        if (a[i][j]) {
            b[i][j][3]=0;
            if (!ok(i+1,j)) continue;
            if (g[i][j][3]) b[i][j][3]=b[i+1][j][3]+1;
        }
    }
//  FOR(i,n) FOR(j,n) f[i][j]=min(b[i][j][1],b[i][j][0]);
    for (int k=2;k<=2*n;k++) {
        for (int i=1;i<=n;i++) {
            if (k-i>=1&&k-i<=n) {
                if (k-1>=1&&k-1<=n) d[i][k-i]=i-1;
                else d[i][k-i]=i-k+n;
            }
        }
    }
    FOR(i,n) FOR(j,n) {
        if (a[i][j]) f[i][j]=d[i][j]-min(b[i][j][1],b[i][j][2]);
        else f[i][j]=-1;    
    }
    for (int k=2;k<=2*n;k++) {
        memset(c,0,sizeof(c));
        tot=0;
        for (int i=1;i<=n;i++) {
            if (k-i>=1&&k-i<=n) {
                t[++tot].v=f[i][k-i];
                t[tot].pos=tot;
                //if (k==n+1) cout<<t[tot].pos<<" ";
            }
        }
        sort(t+1,t+tot+1,cmp);
        //FOR(i,tot) cout<<t[i].v<<" ";
        //cout<<"?";
    //  cout<<endl; 
        if (k==n+1) {
        //  cout<<b[1][4][0]<<" "<<b[1][4][3]<<endl;
        }
        int now=0;
        FOR(i,tot) {
            if (t[i].v<0) {
                continue;
            }
            while (now<=n-abs(k-1-n)-1&&t[i].v>now) {
                int x=0,y=0;
                if (k-1>n) {
                    x=k-n+now,y=n-now;
                } else x=1+now,y=k-1-now;
                cnt[x][y]=query(now+1,now+1+min(b[x][y][0],b[x][y][3]));
                
                now++;
            }
        //  if (k==n+1) cout<<t[i].pos<<" ";
        //  cout<<endl;
            add(t[i].pos,1);
        }
        while (now<=n-abs(k-1-n)-1) {
            int x=0,y=0;
            if (k-1>n) {
                x=k-n+now,y=n-now;
            } else x=1+now,y=k-1-now;
            cnt[x][y]=query(now+1,now+1+min(b[x][y][0],b[x][y][3]));
            now++;
        }
        //if (k==n+1) {
        //  cout<<cnt[1][4]<<endl;
        //}
        
    }
    FOR(i,n) FOR(j,n) ans+=cnt[i][j];
    /*
    FOR(i,n) {
        
        FOR(j,n) cout<<f[i][j]<<" ";
        cout<<endl;
    }*/
    FOR(i,n) FOR(j,n) if (a[i][j]) ans--;
    printf("%d",ans);
    return 0;
}

第一次做离线处理的题目，花了一个下午。
感觉思想就是按照一定的顺序计算使得每次计算的时候数据结构中的元素都是满足当前问题所需的性质的。
特征是问题之间具有叠加性，这就可以找出一种顺序使得前面问题的解也是后面问题的解，每次直接添加新的元素就行了。
写代码的时候犯了很多低级错误，比如：
1.sort的时候t+tot+1写成了t+tot
2.向问题的时候坐标系不统一，一会儿按照直角坐标系，把a[i][j]中的i当作横坐标，一会儿又把i当行数（纵坐标）
3.因为不知道满足当前问题的解有没有全部出现，我选择当出现一个不满足当前问题的解的时候计算这个问题，但是有一种情况就是所有解都可能满足最后问摩，最后一个问题就没人帮它计算了
4.一个解不满足当前问题了，不仅仅转到下一个问题就可以，要用while，直到出现满足的问题
5.计算四个方向最远能达到的距离结果写着就写成了计算四个方向最远能达到的点了（写代码的时候常常掉线，不知道自己之前准备干什么）

当然通过此题训练了一下自己静态查错的能力，经验就是不要反复看一段代码，而是弄清每个变量的意义和自己打算做什么。

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

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

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

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

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

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

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

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

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

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

树状数组~

Orz fjxmlhx。。Orz oimaster。。

我写的很烂的题解和代码（copy 无意义）

http://hi.baidu.com/think%5Fexist/blog/item/c08b55f6c96b19d3f3d3852f.html

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

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

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

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

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

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

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

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

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

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

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

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

zgx你更该收敛吧

终于过了，为什么线段树就超时，为什么要卡常数~ 建议应该把n改为600-700左右。

还有就是vijos sunny 太bug了，超慢，只要叫他测的准TLE。

来膜拜下swj

堆又写错了………………

令left[i][j]表示向左最多能延伸多少，right,up,down同理。

然后枚举左上角，考虑在对角线上，与该点距离min(right,down)之内的点中，有多少的min(up,left)大于与枚举的点的距离即可。

值得注意的是，把所有的问题离线处理可以做到NLOGN.

下面的宋文杰，你难道不怕jzp以其人之道还治其人之身吗？

还是收敛一点吧

编译通过...

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

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

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

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

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

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

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

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

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

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

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

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

树状数组啊~~~一次AC，还是用Dragon过的，爽！

这题是难度5的吧........

我用枚举过了样例，结果评测得0分.............

教主你好，教主再见……

教主我泪目了……

我被虐了……

我真水,总是被tangky的题目虐死......

暴力枚举正方形 40 ……

明明 自己 机子 测 n=1000 只要 2s ……

虽然 是O（n^3）......

等 神牛们 赐教 ……

你可以把线段直接涂到一个数组里

崮rz教主 Orz教主 OTZ教主 ~(≧▽≦)/~啦啦啦~ (≧▽≦)/~啦啦啦 o(≧v≦)o~~好棒 o(≧v≦)o~~好棒

谁能给个思路啊????????????????

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

额