题意：
一个n*n的棋盘，有m个主教。每个主教都有自己的权值p。给出一个值C，在棋盘中找到一个最大点集。这个点集中的点在同一条对角线上且对于点集中任意两点（i，j），i和j之间的主教数（包括i，j）不小于pi^2+pj^2+C。
题解：
对角线有2个方向，每个方向有2*n-1条对角线。一共时4*n-2条。每个点都在2条对角线上。
对于在同一对角线上的点（i，j）若满足i-j+1>=pi^2+pj^2+C即-j-pj^2>=pi^2+C-i-1（i>j)即可。
那么将同一对角线上的点按x坐标排序。将每个点的信息整合到一起离散化，最后用树状数组维护每个点前面满足-j-pj^2>=pi^2+C-i-1的最大值。
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<int, ll> P;
const int maxn = 1e5+;
int t;
int n, m;
ll c;
int u, v;
ll p;
int cnt;
int ans;
ll _sort[maxn<<];
int tree[maxn<<];
struct node {
int x;
ll val;
node(int a, ll b) {
x = a; val = b;
}
};
vector<P> bs[][maxn<<];
void update(int x, int val) {
while(x <= cnt) {
tree[x] = max(tree[x], val);
x += x&(-x);
}
}
int sum(int x) {
int res = ;
while(x > ) {
res = max(res, tree[x]);
x -= x&(-x);
}
return res;
}
int main() {
freopen("bishops.in","r",stdin);
scanf("%d", &t);
while(t--) {
ans = ;
scanf("%d%d%lld", &n, &m, &c);
for(int i = ; i < ; i++)
for(int j = ; j < *n; j++) bs[i][j].clear();
while(m--) {
scanf("%d%d%lld", &u, &v, &p);
p *= p;
bs[][u+v-].push_back(P(u, p));
bs[][u-v+n].push_back(P(u, p));
}
for(int i = ; i < ; i++)
for(int j = ; j < *n; j++) sort(bs[i][j].begin(), bs[i][j].end()); for(int i = ; i < ; i++)
for(int j = ; j < *n; j++) {
int len = bs[i][j].size();
cnt = ;
for(int k = ; k < len; k++) {
int x = bs[i][j][k].first;
ll p = bs[i][j][k].second;
_sort[cnt++] = -p-x;
_sort[cnt++] = p+c-x-;
}
sort(_sort, _sort+cnt);
cnt = unique(_sort, _sort+cnt)-_sort;
for(int k = ; k <= cnt; k++) tree[k] = ;
for(int k = ; k < len; k++) {
int x = bs[i][j][k].first;
ll p = bs[i][j][k].second;
int id = cnt-(lower_bound(_sort, _sort+cnt, p+c-x-)-_sort);
int tmp = sum(id);
ans = max(ans, tmp+);
id = cnt-(lower_bound(_sort, _sort+cnt, -p-x)-_sort);
update(id, tmp+);
}
}
printf("%d\n", ans);
}
}